Algunos antecedentes:
Estoy interesado en encontrar límites inferiores "menos conocidos" (o resultados de dureza) para el problema de Aprendizaje con errores (LWE) y generalizaciones de los mismos como Aprender con errores sobre anillos. Para definiciones específicas, etc., aquí hay una buena encuesta realizada por Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf
El tipo estándar de (R) suposición de estilo LWE es a través de la reducción (quizás, cuántica) al problema de vector más corto en (posiblemente, redes) ideales. Se sabe que la formulación habitual de SVP es NP-dura, y se cree que es difícil aproximarse a pequeños factores polinómicos. (Relacionado: es difícil aproximar el CVP a factores / casi polinomiales: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) También escuché que mencioné eso (en términos de algoritmos cuánticos) La aproximación de ciertos problemas de red (como SVP) a pequeños factores de aproximación polinomiales está relacionada con el problema del subgrupo oculto no abeliano (que se cree que es difícil por sus propios motivos), aunque nunca he visto una fuente explícita y formal para esto.
Sin embargo, estoy más interesado en los resultados de dureza (de cualquier tipo) que surgen como resultado del problema de paridad ruidosa de la teoría del aprendizaje. Estos podrían ser resultados de dureza de la clase de complejidad, límites inferiores algorítmicos concretos, límites de complejidad de la muestra o incluso límites inferiores del tamaño de la prueba (por ejemplo, resolución). Se sabe (tal vez, es obvio) que LWE se puede ver como una generalización del problema de paridad ruidosa / paridad de aprendizaje con ruido (LPN), que (de Google) parece haberse utilizado en reducciones de dureza en áreas como la teoría de codificación y PAC aprendizaje.
Al mirar a mi alrededor, solo he encontrado (ligeramente subexponencial) LÍMITES SUPERIORES en el problema de LPN, por ejemplo, http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf
Pregunta:
Sé que LPN es CREIDO DURO en la comunidad de aprendizaje. Mi pregunta es: ¿por qué?
¿Es porque todos lo intentaron realmente, pero nadie ha encontrado un buen algoritmo todavía? ¿Se conocen límites inferiores de la variedad en cursiva anterior (u otras que he dejado de lado)?
Si la respuesta es muy clara, un resumen sucinto de lo que se conoce y / o referencias a encuestas / notas de clase sería excelente.
Si se desconoce mucho, cuantos más documentos "de vanguardia", mejor. :) (Gracias de antemano!)