gamma-SVP und gamma-HSVP

DMT
Windoof-User
Windoof-User
Beiträge: 25
Registriert: 18. Dez 2007 23:54

gamma-SVP und gamma-HSVP

Beitrag von DMT » 25. Feb 2009 16:48

Hallo,
wir haben im Skript stehen, dass
\(\gamma-HSVP \text{ solves } \gamma^2-SVP\)
Die umgekehrte Richtung haben wir in der Übung 2, Task 5 bewiesen.

Allerdings ist uns die Richtung, welche oben steht, nicht klar.
"Quis custodiet ipsos custodes?"
~Juvenal

mischnei
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 8. Okt 2007 12:51

Re: gamma-SVP und gamma-HSVP

Beitrag von mischnei » 25. Feb 2009 18:46

Hey,

the direction mentioned in the lecture is much harder to prove; you have to use the gamme-HSVP-solver linear many times to solve the SVP with approximation factor gamma^2. Lovasz showed this reduction in 1986 in a paper called "An algorithmic theory of numbers, graphs, and complexity". But it is not at all neccessary to read this proof for the exam.

Additional there are some complexity theretical results that show reductions between both problems; quite interesting but also not required in our lecture :-)

So far

Michael

Antworten

Zurück zu „Archiv“