Euclidean SVP is deterministically NP-hard to approximate within any constant factor

Technische Samenvatting: Deterministische NP-hardheid van de Euclidische SVP-benadering

Probleemstelling
Het artikel behandelt de computationele complexiteit van het Euclidische Shortest Vector Problem (SVP). Specifiek onderzoekt het het $\rho$-GapSVP probleem: gegeven een integraal roosterbasis en een drempelwaarde $d$, onderscheid tussen het geval waarbij de kortste niet-nul vector een lengte heeft $\lambda_2(L) \le d$ (JA) en het geval waarbij $\lambda_2(L) > \rho d$ (NEE), voor een constante benaderingsfactor $\rho > 1$.

Vóór dit werk was de deterministische NP-hardheid van het benaderen van het Euclidische SVP beperkt tot factoren $\rho < \sqrt{2}$. Hoewel gerandomiseerde reducties de hardheid voor willekeurige constante factoren (Khot [22]) en zelfs bijna-polynomiale factoren (Haviv en Regev [19]) vaststelden, bleef de derandomisering van deze resultaten voor de Euclidische ruimte meer dan een decennium lang een open uitdaging. Het gebrek aan multiplicatieve eigenschappen van de Euclidische norm onder tensorproducten, in tegenstelling tot de Hamming-afstand in de coderingstheorie, was een primaire hindernis.

Methodologie
De auteur construeert een deterministische polynomiale-tijd veel-op-één reductie van een NP-volledig probleem naar Euclidische $\rho$-GapSVP voor elke constante $\rho > 1$. De bewijsstrategie rust op drie componenten:

1. Constructie van een Deterministische Binaire $\ell_1$ Gap:
   De auteur construeert eerst een rooster met een "binaire gap" in de $\ell_1$-norm. Ze combineren een deterministische reductie van Gap Exact Set Cover met een Reed–Solomon lokaal dicht rooster gadget.

   • De Set Cover-reductie (gebaseerd op Micciancio [27] en Bennett–Peikert [9]) creëert een broninstantie waarbij JA-instanties een binaire vector met een lage gewicht opleveren, terwijl NEE-instanties alle niet-nul gehele vectoren dwingen een hoge support te hebben.
   • De Reed–Solomon gadget (afgeleid van het eerdere werk van de auteur [36]) zorgt ervoor dat er voor elke voorgeschreven binaire projectie een roostervector in een specifieke coset bestaat die binair is en een $\ell_1$-norm heeft die net boven de helft van het minimum van het rooster ligt.
   • Door deze via een blok-embedding te combineren, produceren ze een rooster $L$ en drempelwaarde $d$ zodanig dat:
     • JA: Er bestaat een binaire vector $y \in L \cap \{0,1\}^N$ met $\|y\|_1 < d$.
     • NEE: Voor alle niet-nul $x \in L$, geldt $\|x\|_1 \ge \eta d$, waarbij $1 < \eta < 2$ een vaste constante is.

2. Exacte $\ell_1$ Tensor Identiteit:
   Een cruciale theoretische bijdrage is het bewijs dat de minimale $\ell_1$-norm van een integraal rooster multiplicatief is onder tensorproducten.

   • In tegenstelling tot de Euclidische norm ($\ell_2$), waarbij de kortste vector in een tensorproductrooster $L_1 \otimes L_2$ niet noodzakelijkerwijs een zuivere tensor is (en dus $\lambda_2(L_1 \otimes L_2) \neq \lambda_2(L_1)\lambda_2(L_2)$), voldoet de minimale $\ell_1$-norm aan de exacte identiteit:
     $$\lambda(L_1 \otimes \dots \otimes L_t) = \prod_{i=1}^t \lambda(L_i)$$
   • Dit resultaat wordt vastgesteld door de minimale $\ell_1$-norm van een rooster te relateren aan het minimale Lee-gewicht van een quotientcode over gehele residu-ringen. De auteur maakt gebruik van de Ojiro–Matsui productformule voor Lee-gewichten [29] om deze multipliciteit voor vol-rank roosters te bewijzen en dit via een completion-argument uit te breiden naar willekeurige rank-roosters.

3. Tensor Amplificatie:
   De auteur neemt de $t$-voudige tensor macht van het basisrooster $L$ geconstrueerd in stap 1.

   • In het JA-geval blijft de vector $y^{\otimes t}$ binair. Aangezien binaire vectoren voldoen aan $\|v\|_2^2 = \|v\|_1$, wordt de Euclidische lengte $\|y^{\otimes t}\|_2 = \|y\|_1^{t/2} < d^{t/2}$.
   • In het NEE-geval zorgt de multiplicatieve eigenschap van de $\ell_1$-norm ervoor dat $\lambda(L^{\otimes t}) = \lambda(L)^t \ge (\eta d)^t$. Gebruikmakend van de ongelijkheid $\|x\|_2 \ge \|x\|_1^{1/2}$ (voor gehele vectoren), wordt de Euclidische lengte ondergrenzen door $(\eta d)^{t/2}$.
   • De resulterende benaderingsgap is $\eta^{t/2}$. Door een voldoende grote constante $t$ te kiezen, kan de gap elke gewenste constante $\rho$ overtreffen.

Belangrijkste Resultaten

• Theorem 1.2 (Hoofdtheorema): Voor elke constante $\rho > 1$ is Euclidische $\rho$-GapSVP NP-hard onder een deterministische polynomiale-tijd veel-op-één reductie. Dit biedt een deterministisch tegenhanger voor Khots gerandomiseerde stelling.
• Theorem 1.4 (Alle Eindige Normen): Het resultaat breidt zich uit naar alle vaste eindige $\ell_p$-normen ($1 \le p < \infty$). Voor elke vaste $p$ en constante $\rho > 1$ is $\rho$-GapSVP$_p$ deterministisch NP-hard.
• Theorem 1.5 (Dimensie-afhankelijke Regimes): Door de tensororde $t$ te laten meegroeien met de inputgrootte (in plaats van een vaste constante), leidt de auteur deterministische versies af van de dimensie-afhankelijke hardheidsregimes die voorheen alleen bekend waren via gerandomiseerde reducties:
  • Quasi-polynomiale-tijd reducties: Hardheid voor factoren $2^{(\log n)^{1-\varepsilon}}$.
  • Subexponentiële-tijd reducties: Hardheid voor factoren $n^{c/\log \log n}$.

Betekenis en Claims
Het artikel claimt een langdurig openstaand probleem in de rooster-gebaseerde complexiteit te hebben opgelost door de noodzaak van randomisatie te verwijderen bij het bewijzen van de NP-hardheid van het benaderen van het Euclidische SVP voor willekeurige constante factoren.

• Derandomisering: Het werk slaagt erin de reductie voor het Euclidische SVP te derandomiseren, een taak die voorgaande pogingen weerstond vanwege de moeilijkheid van het construeren van deterministische lokaal dichte roosters in de Euclidische ruimte.
• Methodologische Verschuiving: Het bewijs probeert niet Khots constructie regel voor regel te derandomiseren. In plaats daarvan introduceert het een nieuwe structurele aanpak: het gebruik van een deterministische binaire gadget om een $\ell_1$ gap te creëren, en vervolgens gebruik te maken van de exacte multiplicativiteit van de $\ell_1$-norm onder tensorproducten om deze gap te versterken in het Euclidische domein.
• Coderingstheoretische Analogie: Het artikel benadrukt een diepe connectie tussen roosterproblemen en de coderingstheorie. Net zoals de minimale Hamming-afstand van lineaire codes multiplicatief is onder tensorproducten, laat de auteur zien dat de minimale $\ell_1$-norm van integrale roosters (via de Lee-metriek) deze eigenschap deelt, waardoor amplificatietechnieken uit de coderingstheorie naar roosters kunnen worden overgedragen.
• Vergelijking met Voorgaand Werk: De auteur merkt op dat hoewel Hair en Sahai [18] recentelijk deterministische hardheid voor willekeurige constanten hebben verkregen, hun resultaat vertrouwde op een PCP-benadering en subexponentiële-tijd reducties. Dit artikel verbetert dit door het resultaat te bereiken via polynomiale-tijd reducties.

Het artikel concludeert dat hoewel de tensor-amplificatiemethode een natuurlijke limiet heeft (het levert factoren $n^{o(1)}$ op in plaats van $n^\varepsilon$ voor een vaste $\varepsilon$), het succesvol de deterministische hardheid van constante-factor benadering voor het Euclidische SVP en alle eindige $\ell_p$-normen vaststelt.