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

Sintesi Tecnica: NP-Hardness Deterministica dell'Approssimazione del SVP Euclideo

Enunciato del Problema
Il documento affronta la complessità computazionale del problema del Vettore Più Corto Euclideo (SVP). Nello specifico, investiga il problema $\rho$-GapSVP: dato una base di un reticolo integrale e una soglia $d$, distinguere tra il caso in cui il vettore non nullo più corto ha lunghezza $\lambda_2(L) \le d$ (SÌ) e il caso in cui $\lambda_2(L) > \rho d$ (NO), per un fattore di approssimazione costante $\rho > 1$.

Prima di questo lavoro, l'NP-hardness deterministica dell'approssimazione dello SVP euclideo era limitata a fattori $\rho < \sqrt{2}$. Sebbene le riduzioni randomizzate avessero stabilito l'indurimento per arbitrari fattori costanti (Khot [22]) e persino per fattori quasi-polinomiali (Haviv e Regev [19]), la derandomizzazione di questi risultati per lo spazio euclideo rimaneva una sfida aperta per oltre un decennio. La mancanza di proprietà multiplicative sotto prodotti tensoriali della norma euclidea, a differenza della distanza di Hamming nella teoria dei codici, è stata un ostacolo primario.

Metodologia
L'autore costruisce una riduzione deterministica polinomiale many-one da un problema NP-completo allo $\rho$-GapSVP euclideo per ogni costante $\rho > 1$. La strategia di prova si basa su tre componenti principali:

1. Costruzione di un Gap Binario $\ell_1$ Deterministico:
   L'autore costruisce prima un reticolo con un "gap binario" nella norma $\ell_1$. Combina una riduzione deterministica da Gap Exact Set Cover con un gadget di reticolo localmente denso di tipo Reed–Solomon.

   • La riduzione di Set Cover (basata su Micciancio [27] e Bennett–Peikert [9]) crea un'istanza sorgente in cui le istanze SÌ producono un vettore binario a basso peso, mentre le istanze NO costringono tutti i vettori interi non nulli ad avere un alto supporto.
   • Il gadget Reed–Solomon (derivato dal lavoro precedente dell'autore [36]) assicura che, per ogni proiezione binaria prescritta, esista un vettore di reticolo in una specifica coset che sia binario e abbia una norma $\ell_1$ leggermente superiore alla metà del minimo del reticolo.
   • Combinandoli tramite un embedding a blocchi, si produce un reticolo $L$ e una soglia $d$ tali che:
     • SÌ: Esiste un vettore binario $y \in L \cap \{0,1\}^N$ con $\|y\|_1 < d$.
     • NO: Per ogni $x \in L$ non nullo, $\|x\|_1 \ge \eta d$, dove $1 < \eta < 2$ è una costante fissa.

2. Identità Tensoriale Esatta $\ell_1$:
   Un contributo teorico critico è la dimostrazione che la norma $\ell_1$ minima di un reticolo integrale è multiplicativa sotto prodotti tensoriali.

   • A differenza della norma euclidea ($\ell_2$), dove il vettore più corto in un reticolo prodotto tensoriale $L_1 \otimes L_2$ non deve necessariamente essere un tensore puro (e quindi $\lambda_2(L_1 \otimes L_2) \neq \lambda_2(L_1)\lambda_2(L_2)$), il minimo $\ell_1$ soddisfa l'identità esatta:
     $$\lambda(L_1 \otimes \dots \otimes L_t) = \prod_{i=1}^t \lambda(L_i)$$
   • Questo risultato è stabilito collegando il minimo $\ell_1$ di un reticolo al peso minimo di Lee di un codice quotient su anelli residui interi. L'autore utilizza la formula del prodotto di Ojiro–Matsui per i pesi di Lee [29] per provare questa moltiplicatività per reticoli a pieno rango ed estenderla a reticoli di rango arbitrario tramite un argomento di completamento.

3. Amplificazione Tensoriale:
   L'autore prende la potenza tensoriale $t$-esima del reticolo base $L$ costruito nel passaggio 1.

   • Nel caso SÌ, il vettore $y^{\otimes t}$ rimane binario. Poiché i vettori binari soddisfano $\|v\|_2^2 = \|v\|_1$, la lunghezza euclidea diventa $\|y^{\otimes t}\|_2 = \|y\|_1^{t/2} < d^{t/2}$.
   • Nel caso NO, la proprietà moltiplicativa della norma $\ell_1$ assicura che $\lambda(L^{\otimes t}) = \lambda(L)^t \ge (\eta d)^t$. Utilizzando la disuguaglianza $\|x\|_2 \ge \|x\|_1^{1/2}$ (per vettori interi), la lunghezza euclidea è limitata inferiormente da $(\eta d)^{t/2}$.
   • Il gap di approssimazione risultante è $\eta^{t/2}$. Scegliendo un valore costante $t$ sufficientemente grande, il gap può superare qualsiasi costante $\rho$ desiderato.

Risultati Chiave

• Teorema 1.2 (Teorema Principale): Per ogni costante $\rho > 1$, lo $\rho$-GapSVP euclideo è NP-hard sotto una riduzione many-one deterministica in tempo polinomiale. Questo fornisce un contrappunto deterministico al teorema randomizzato di Khot.
• Teorema 1.4 (Tutte le Norme Finite): Il risultato si estende a tutte le norme $\ell_p$ finite fissate ($1 \le p < \infty$). Per ogni $p$ fisso e costante $\rho > 1$, lo $\rho$-GapSVP$_p$ è deterministicamente NP-hard.
• Teorema 1.5 (Regimi Dipendenti dalla Dimensione): Permettendo all'ordine del tensore $t$ di crescere con la dimensione dell'input (anziché essere una costante fissa), l'autore deriva versioni deterministiche degli indurimenti nei regimi dipendenti dalla dimensione precedentemente noti solo tramite riduzioni randomizzate:
  • Riduzioni in tempo quasi-polinomiale: Indurimento per fattori $2^{(\log n)^{1-\varepsilon}}$.
  • Riduzioni in tempo subesponenziale: Indurimento per fattori $n^{c/\log \log n}$.

Significato e Rivendicazioni
Il documento sostiene di aver risolto un problema aperto di lunga data nella complessità basata sui reticoli, eliminando la necessità di casualità per provare l'NP-hardness dell'approssimazione dello SVP euclideo per arbitrari fattori costanti.

• Derandomizzazione: Il lavoro derandomizza con successo la riduzione per lo SVP euclideo, un compito che aveva resistito ai tentativi precedenti a causa della difficoltà di costruire reticoli localmente densi deterministici nello spazio euclideo.
• Spostamento Metodologico: La prova non tenta di derandomizzare la costruzione di Khot riga per riga. Invece, introduce un nuovo approccio strutturale: utilizzare un gadget binario deterministico per creare un gap $\ell_1$ e poi sfruttare la moltiplicatività esatta della norma $\ell_1$ sotto prodotti tensoriali per amplificare questo gap nel dominio euclideo.
• Analogia con la Teoria dei Codici: Il documento evidenzia una profonda connessione tra i problemi dei reticoli e la teoria dei codici. Proprio come la distanza di Hamming minima dei codici lineari è moltiplicativa sotto prodotti tensoriali, l'autore mostra che la norma $\ell_1$ minima dei reticoli integrali (tramite la metrica di Lee) condivide questa proprietà, permettendo il trasferimento delle tecniche di amplificazione dalla teoria dei codici ai reticoli.
• Confronto con il Lavoro Precedente: L'autore nota che, sebbene Hair e Sahai [18] abbiano recentemente ottenuto l'indurimento deterministico per costanti arbitrarie, il loro risultato si basava su un approccio PCP e riduzioni in tempo subesponenziale. Questo lavoro migliora tale risultato ottenendo il risultato tramite riduzioni in tempo polinomiale.

Il documento conclude che, sebbene il metodo di amplificazione tensoriale abbia un limite naturale (producendo fattori $n^{o(1)}$ anziché $n^\varepsilon$ per $\varepsilon$ fissi), esso stabilisce con successo l'indurimento deterministico della costante-approssimazione per lo SVP euclideo e per tutte le norme $\ell_p$ finite.