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

Résumé Technique : NP-Dureté Déterministe de l'Approximation du SVP Euclidien

Énoncé du Problème
L'article traite de la complexité computationnelle du problème du vecteur le plus court euclidien (SVP). Plus précisément, il étudie le problème $\rho$-GapSVP : étant donné une base de réseau intégral et un seuil $d$, distinguer le cas où le vecteur non nul le plus court a une longueur $\lambda_2(L) \le d$ (OUI) du cas où $\lambda_2(L) > \rho d$ (NON), pour un facteur d'approximation constant $\rho > 1$.

Avant ce travail, la NP-dureté déterministe de l'approximation du SVP euclidien était limitée à des facteurs $\rho < \sqrt{2}$. Bien que des réductions aléatoires aient établi la dureté pour des facteurs constants arbitraires (Khot [22]), et même pour des facteurs quasi-polynomials (Haviv et Regev [19]), la dérandomisation de ces résultats pour l'espace euclidien est restée un défi ouvert pendant plus d'une décennie. L'absence de propriétés multiplicatives de la norme euclidienne sous les produits tensoriels, contrairement à la distance de Hamming dans la théorie des codes, constituait un obstacle majeur.

Méthodologie
L'auteur construit une réduction déterministe polynomiale de type "many-one" d'un problème NP-complet vers le $\rho$-GapSVP euclidien pour tout $\rho > 1$ constant. La stratégie de preuve repose sur trois composantes principales :

1. Construction de Gap Binaire $\ell_1$ Déterministe :
   L'auteur construit d'abord un réseau présentant un « gap binaire » dans la norme $\ell_1$. Il combine une réduction déterministe de Gap Exact Set Cover avec un gadget de réseau localement dense de type Reed–Solomon.

   • La réduction de Set Cover (basée sur Micciancio [27] et Bennett–Peikert [9]) crée une instance source où les instances OUI produisent un vecteur binaire de faible poids, tandis que les instances NON forcent tous les vecteurs entiers non nuls à avoir un support élevé.
   • Le gadget Reed–Solomon (dérivé des travaux précédents de l'auteur [36]) garantit que pour toute projection binaire prescrite, il existe un vecteur de réseau dans une coset spécifique qui est binaire et possède une norme $\ell_1$ légèrement supérieure à la moitié du minimum du réseau.
   • En combinant ces éléments via un plongement par blocs, l'auteur produit un réseau $L$ et un seuil $d$ tels que :
     • OUI : Il existe un vecteur binaire $y \in L \cap \{0,1\}^N$ avec $\|y\|_1 < d$.
     • NON : Pour tout $x \in L$ non nul, $\|x\|_1 \ge \eta d$, où $1 < \eta < 2$ est une constante fixée.

2. Identité Tensorielle Exacte de la Norme $\ell_1$ :
   Une contribution théorique cruciale est la preuve que la norme $\ell_1$ minimale d'un réseau intégral est multiplicative sous les produits tensoriels.

   • Contrairement à la norme euclidienne ($\ell_2$), où le vecteur le plus court dans un réseau produit tensoriel $L_1 \otimes L_2$ n'est pas nécessairement un tenseur pur (et donc $\lambda_2(L_1 \otimes L_2) \neq \lambda_2(L_1)\lambda_2(L_2)$), le minimum $\ell_1$ satisfait l'identité exacte :
     $$\lambda(L_1 \otimes \dots \otimes L_t) = \prod_{i=1}^t \lambda(L_i)$$
   • Ce résultat est établi en reliant le minimum $\ell_1$ d'un réseau au poids Lee minimum d'un code quotient sur des anneaux résiduels entiers. L'auteur utilise la formule de produit d'Ojiro–Matsui pour les poids Lee [29] afin de prouver cette multiplicativité pour les réseaux de plein rang, puis de l'étendre aux réseaux de rang arbitraire via un argument de complétion.

3. Amplification Tensorielle :
   L'auteur prend la puissance tensorielle $t$-uple du réseau de base $L$ construit à l'étape 1.

   • Dans le cas OUI, le vecteur $y^{\otimes t}$ reste binaire. Comme les vecteurs binaires satisfont $\|v\|_2^2 = \|v\|_1$, la longueur euclidienne devient $\|y^{\otimes t}\|_2 = \|y\|_1^{t/2} < d^{t/2}$.
   • Dans le cas NON, la propriété multiplicative de la norme $\ell_1$ garantit que $\lambda(L^{\otimes t} = \lambda(L)^t \ge (\eta d)^t$. En utilisant l'inégalité $\|x\|_2 \ge \|x\|_1^{1/2}$ (pour les vecteurs entiers), la longueur euclidienne est bornée inférieurement par $(\eta d)^{t/2}$.
   • Le gap d'approximation résultant est $\eta^{t/2}$. En choisissant un $t$ constant suffisamment grand, le gap peut dépasser n'importe quel $\rho$ constant désiré.

Résultats Clés

• Théorème 1.2 (Théorème Principal) : Pour tout $\rho > 1$ constant, le $\rho$-GapSVP euclidien est NP-dur sous une réduction déterministe polynomiale de type many-one. Cela fournit un contrepartie déterministe au théorème aléatoire de Khot.
• Théorème 1.4 (Toutes les Normes Finies) : Le résultat s'étend à toutes les normes $\ell_p$ finies fixées ($1 \le p < \infty$). Pour tout $p$ fixé et $\rho > 1$ constant, le $\rho$-GapSVP$_p$ est déterministement NP-dur.
• Théorème 1.5 (Régimes Dépendants de la Dimension) : En permettant à l'ordre tensoriel $t$ de croître avec la taille de l'entrée (plutôt que d'être une constante fixe), l'auteur dérive des versions déterministes des régimes de dureté dépendants de la dimension, connus auparavant uniquement via des réductions aléatoires :
  • Réductions en temps quasi-polynomial : Dureté pour des facteurs $2^{(\log n)^{1-\varepsilon}}$.
  • Réductions en temps sous-exponentiel : Dureté pour des facteurs $n^{c/\log \log n}$.

Signification et Revendications
L'article affirme résoudre un problème ouvert de longue date dans la complexité des réseaux en supprimant le besoin de l'aléa pour prouver la NP-dureté de l'approximation du SVP euclidien pour des facteurs de constante arbitraires.

• Dérandomisation : Ce travail dérandomise avec succès la réduction pour le SVP euclidien, une tâche qui avait résisté aux tentatives précédentes en raison de la difficulté de construire des réseaux localement denses de manière déterministe dans l'espace euclidien.
• Changement de Méthodologie : La preuve ne tente pas de dérandomiser la construction de Khot ligne par ligne. Au lieu de cela, elle introduit une nouvelle approche structurelle : utiliser un gadget binaire déterministe pour créer un gap $\ell_1$, puis exploiter la multiplicativité exacte de la norme $\ell_1$ sous les produits tensoriels pour amplifier ce gap dans le domaine euclidien.
• Analogie avec la Théorie des Codes : L'article souligne un lien profond entre les problèmes de réseaux et la théorie des codes. Tout comme la distance de Hamming minimale des codes linéaires est multiplicative sous les produits tensoriels, l'auteur montre que la norme $\ell_1$ minimale des réseaux intégraux (via la métrique de Lee) partage cette propriété, permettant ainsi le transfert des techniques d'amplification de la théorie des codes vers les réseaux.
• Comparaison avec les Travaux Antérieurs : L'auteur note que bien que Hair et Sahai [18] aient récemment obtenu une dureté déterministe pour des constantes arbitraires, leur résultat reposait sur une approche PCP et des réductions en temps sous-exponentiel. Ce papier améliore ce résultat en l'atteignant via des réductions en temps polynomial.

L'article conclut que, bien que la méthode d'amplification tensorielle possède un plafond naturel (produisant des facteurs de $n^{o(1)}$ plutôt que $n^\varepsilon$ pour un $\varepsilon$ fixé), elle établit avec succès la dureté déterministe de l'approximation à facteur constant pour le SVP euclidien et toutes les normes $\ell_p$ finies.