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

Resumen Técnico: Dureza NP-Hard Determinista de la Aproximación del SVP Euclídeo

Declaración del Problema
El artículo aborda la complejidad computacional del Problema del Vector Más Corto (SVP) euclídeo. Específicamente, investiga el problema $\rho$-GapSVP: dada una base de red integral y un umbral $d$, distinguir entre el caso donde la longitud del vector no nulo más corto es $\lambda_2(L) \le d$ (SÍ) y el caso donde $\lambda_2(L) > \rho d$ (NO), para un factor de aproximación constante $\rho > 1$.

Antes de este trabajo, la dureza NP determinista de la aproximación del SVP euclídeo se limitaba a factores $\rho < \sqrt{2}$. Si bien las reducciones aleatorizadas establecieron la dureza para factores constantes arbitrarios (Khot [22]) e incluso para factores casi polinómicos (Haviv y Regev [19]), la derandomización de estos resultados para el espacio euclídeo permaneció como un desafío abierto durante más de una década. La falta de propiedades multiplicativas de la norma euclídea bajo productos tensoriales, a diferencia de la distancia de Hamming en la teoría de códigos, fue un obstáculo principal.

Metodología
El autor construye una reducción determinista de tiempo polinomial de uno a uno desde un problema NP-completo hacia el $\rho$-GapSVP euclídeo para cualquier constante $\rho > 1$. La estrategia de prueba se basa en tres componentes:

1. Construcción Determinista de Brecha Binaria $\ell_1$:
   El autor construye primero una red con una "brecha binaria" en la norma $\ell_1$. Combina una reducción determinista de Gap Exact Set Cover con un gadget de red localmente densa de Reed–Solomon.

   • La reducción de Set Cover (basada en Micciancio [27] y Bennett–Peikert [9]) crea una instancia de origen donde las instancias SÍ producen un vector binario de bajo peso, mientras que las instancias NO fuerzan a todos los vectores enteros no nulos a tener un soporte alto.
   • El gadget de Reed–Solomon (derivado del trabajo previo del autor [36]) asegura que, para cualquier proyección binaria prescrita, exista un vector de red en un coset específico que sea binario y tenga una norma $\ell_1$ ligeramente superior a la mitad del mínimo de la red.
   • Al combinar estos mediante un incrustamiento por bloques, producen una red $L$ y un umbral $d$ tales que:
     • SÍ: Existe un vector binario $y \in L \cap \{0,1\}^N$ con $\|y\|_1 < d$.
     • NO: Para todo $x \in L$ no nulo, $\|x\|_1 \ge \eta d$, donde $1 < \eta < 2$ es una constante fija.

2. Identidad Tensorial Exacta de $\ell_1$:
   Una contribución teórica crítica es la demostración de que el mínimo de la norma $\ell_1$ de una red integral es multiplicativo bajo productos tensoriales.

   • A diferencia de la norma euclídea ($\ell_2$), donde el vector más corto en un producto tensorial de redes $L_1 \otimes L_2$ no tiene por qué ser un tensor puro (y, por lo tanto, $\lambda_2(L_1 \otimes L_2) \neq \lambda_2(L_1)\lambda_2(L_2)$), el mínimo $\ell_1$ satisface la identidad exacta:
     $$\lambda(L_1 \otimes \dots \otimes L_t) = \prod_{i=1}^t \lambda(L_i)$$
   • Este resultado se establece relacionando el mínimo $\ell_1$ de una red con el peso Lee mínimo de un código cociente sobre anillos de residuos enteros. El autor utiliza la fórmula de producto de Ojiro–Matsui para pesos Lee [29] para probar esta multiplicidad para redes de rango completo y extenderla a redes de rango arbitrario mediante un argumento de completación.

3. Amplificación Tensorial:
   El autor toma la potencia tensorial $t$-doble de la red base $L$ construida en el paso 1.

   • En el caso SÍ, el vector $y^{\otimes t}$ sigue siendo binario. Dado que los vectores binarios satisfacen $\|v\|_2^2 = \|v\|_1$, la longitud euclídea se convierte en $\|y^{\otimes t}\|_2 = \|y\|_1^{t/2} < d^{t/2}$.
   • En el caso NO, la propiedad multiplicativa de la norma $\ell_1$ asegura que $\lambda(L^{\otimes t}) = \lambda(L)^t \ge (\eta d)^t$. Usando la desigualdad $\|x\|_2 \ge \|x\|_1^{1/2}$ (para vectores enteros), la longitud euclídea está acotada inferiormente por $(\eta d)^{t/2}$.
   • La brecha de aproximación resultante es $\eta^{t/2}$. Al elegir un valor constante $t$ suficientemente grande, la brecha puede exceder cualquier constante $\rho$ deseado.

Resultados Clave

• Teorema 1.2 (Teorema Principal): Para cada constante $\rho > 1$, el $\rho$-GapSVP euclídeo es NP-duro bajo una reducción determinista de tiempo polinomial de uno a uno. Esto proporciona un contraparte determinista al teorema aleatorizado de Khot.
• Teoremo 1.4 (Todas las Normas Finitas): El resultado se extiende a todas las normas $\ell_p$ finitas fijas ($1 \le p < \infty$). Para cualquier $p$ fijo y constante $\rho > 1$, el $\rho$-GapSVP$_p$ es deterministamente NP-duro.
• Teorema 1.5 (Regímenes Dependientes de la Dimensión): Al permitir que el orden del tensor $t$ crezca con el tamaño de la entrada (en lugar de ser una constante fija), el autor deriva versiones deterministas de los regímenes de dureza dependientes de la dimensión previamente conocidos solo mediante reducciones aleatorizadas:
  • Reducciones de tiempo cuasi-polinomial: Dureza para factores $2^{(\log n)^{1-\varepsilon}}$.
  • Reducciones de tiempo subexponencial: Dureza para factores $n^{c/\log \log n}$.

Significado y Reivindicaciones
El artículo afirma resolver un problema abierto de larga data en la complejidad basada en redes al eliminar la necesidad de aleatoriedad para probar la dureza NP de la aproximación del SVP euclídeo para factores constantes arbitrarios.

• Derandomización: El trabajo logra con éxito la derandomización de la reducción para el SVP euclídeo, una tarea que resistió intentos previos debido a la dificultad de construir redes localmente densas deterministas en el espacio euclídeo.
• Cambio Metodológico: La prueba no intenta derandomizar la construcción de Khot línea por línea. En su lugar, introduce un enfoque estructural nuevo: usar un gadget binario determinista para crear una brecha $\ell_1$, y luego aprovechar la multiplicidad exacta de la norma $\ell_1$ bajo productos tensoriales para amplificar esta brecha hacia el dominio euclídeo.
• Analogía con la Teoría de Códigos: El artículo destaca una conexión profunda entre los problemas de redes y la teoría de códigos. Así como la distancia de Hamming mínima de los códigos lineales es multiplicativa bajo productos tensoriales, el autor muestra que el mínimo de la norma $\ell_1$ de las redes integrales (vía la métrica de Lee) comparte esta propiedad, permitiendo la transferencia de técnicas de amplificación de la teoría de códigos a las redes.
• Comparación con Trabajos Previos: El autor señala que, si bien Hair y Sahai [18] obtuvieron recientemente dureza determinista para constantes arbitrarias, su resultado dependía de un enfoque PCP y reducciones de tiempo subexponencial. Este artículo mejora esto al lograr el resultado mediante reducciones de tiempo polinomial.

El artículo concluye que, si bien el método de amplificación tensorial tiene un límite natural (produciendo factores de $n^{o(1)}$ en lugar de $n^\varepsilon$ para un $\varepsilon$ fijo), logra establecer con éxito la dureza determinista de la aproximación de factor constante para el SVP euclídeo y todas las normas $\ell_p$ finitas.