Alguns antecedentes:
Estou interessado em encontrar limites inferiores "menos conhecidos" (ou resultados de dureza) para o problema de Aprendizagem com erros (LWE) e generalizações dos mesmos, como Aprender com erros por anéis. Para definições específicas, etc., aqui está uma boa pesquisa da Regev: http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf
O tipo padrão de suposição no estilo (R) LWE é via (talvez quântica) a redução do Problema de Vetor Mais Curto em redes (talvez, ideais). A formulação usual de SVP é conhecida por ser NP-difícil, e acredita-se que seja difícil aproximar-se de pequenos fatores polinomiais. (Relacionado: É difícil aproximar o CVP de fatores internos / quase polinomiais /: http://dl.acm.org/citation.cfm?id=1005180.1005182 ) Também ouvi falar disso (em termos de algoritmos quânticos) aproximar certos problemas de rede (como SVP) a pequenos fatores de aproximação polinomial está relacionado ao problema de subgrupo oculto não abeliano (que se acredita ser difícil por suas próprias razões), embora eu nunca tenha visto uma fonte formal explícita para isso.
No entanto, estou mais interessado nos resultados de dureza (de qualquer tipo) resultantes do problema de paridade ruidosa da teoria de aprendizagem. Podem ser resultados de dureza da classe de complexidade, limites inferiores algorítmicos concretos, limites de complexidade da amostra ou mesmo limites inferiores do tamanho da prova (por exemplo, Resolução). Sabe-se (talvez, óbvio) que o LWE pode ser visto como uma generalização do problema Paridade ruidosa / Paridade de aprendizado com ruído (LPN), que (do Google) parece ter sido usada na redução de dureza em áreas como a teoria de codificação e o PAC Aprendendo.
Ao olhar em volta de mim, apenas encontrei (levemente subexponencial) CAIXAS SUPERIORES no problema LPN, por exemplo, http://www.di.ens.fr/~lyubash/papers/parityproblem.pdf
Questão:
Eu sei que o LPN é ACREDITADO DURAMENTE na comunidade de aprendizagem. Minha pergunta é: por quê?
É porque todo mundo se esforçou muito, mas ninguém encontrou um bom algoritmo ainda? Existem limites inferiores conhecidos da variedade em itálico acima (ou outros que eu deixei de fora)?
Se a resposta for muito clara, seria ótimo um resumo sucinto do que é conhecido e / ou referências a pesquisas / notas de aula.
Se muita coisa é desconhecida, quanto mais artigos "de última geração", melhor. :) (Agradecemos antecipadamente!)
fonte