Seite 1 von 1

gamma-SVP und gamma-HSVP

Verfasst: 25. Feb 2009 16:48
von DMT
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.

Re: gamma-SVP und gamma-HSVP

Verfasst: 25. Feb 2009 18:46
von mischnei
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