Melhor complexidade de consulta do algoritmo de aprendizado Goldreich-Levin / Kushilevitz-Mansour

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/\epsilon^4 n \log n)$$n$

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 \log^3(1/\epsilon))$$n^2$$n$$\Omega(\epsilon^2)$$2/3$${\tilde O}(n/\epsilon^2)$