Qual é a complexidade de consulta mais conhecida do algoritmo de aprendizado Goldreich-Levin? As notas da palestra do blog de Luca Trevisan , Lemma 3, afirmam . Isso é o mais conhecido em termos de dependência de n ? Ficarei particularmente grato por uma referência a uma fonte citável!O ( 1 / ϵ4n logn )O(1/ϵ4nregistro⁡n)nn
Pergunta relacionada: qual é a complexidade de consulta mais conhecida do algoritmo de aprendizado Kushilevitz-Mansour?
A questão parece um pouco subespecificada no sentido de que não especificou a probabilidade de erro desejada do procedimento. Supondo que um signifique probabilidade de erro constante, o exposto acima é realmente o melhor que conheço. Para uma discussão detalhada, consulte a Seção 2.5.2.4 no meu livro "The Foundations of Cryptography - Volume 1" disponível em http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html
O ACIMA ESTÁ ERRADO. VEJA A RESPOSTA CORRIGIDA ABAIXO.
O suporte 2.5.6 na seção acima mencionada mostra um limite muito melhor: o algoritmo é executado no tempo esperado vezes o tempo de execução do procedimento de adivinhação (consulte a melhoria de n 2 para n no comentário logo após a prova) e está correto wp Ω ( ϵ 2 ) . Por isso, a correcção wp 2 / 3 é obtido em tempo (fator) ~ S ( n / ε 2 ) , o que é óptimo, em algum sentido (ver Exer 30).O ( n log3( 1 / ϵ ) )O(nregistro3⁡(1/ϵ))n2n2nnΩ ( ϵ2)Ω(ϵ2)2 / 32/3O~( n / ϵ2)O~(n/ϵ2)
A história (do meu erro): Ao ver esta pergunta, apenas olhei para a seção mencionada, li a afirmação errada (devido à pressa) e apenas respondi sem pensar. Mais tarde, lembrei-me vagamente que uma vez me fizeram a mesma pergunta e respondi de maneira diferente. Então, eu verifiquei com mais cuidado. Lições (que eu deveria saber): Não faça as coisas às pressas; não aja com o pensamento ...