Meilleure complexité des requêtes de l'algorithme d'apprentissage Goldreich-Levin / Kushilevitz-Mansour

14

Quelle est la complexité de requête la plus connue de l'algorithme d'apprentissage Goldreich-Levin? Les notes de cours du blog de Luca Trevisan , Lemma 3, l'indiquent comme . Est-ce le plus connu en termes de dépendance à n ? Je serai particulièrement reconnaissant pour une référence à une source citable!O(1/ϵ4nlogn)n

Question connexe: quelle est la complexité de requête la plus connue de l'algorithme d'apprentissage de Kushilevitz-Mansour?

Grigory Yaroslavtsev
la source

Réponses:

19

La question semble quelque peu sous-spécifiée en ce sens qu'elle n'a pas précisé la probabilité d'erreur souhaitée de la procédure. En supposant que l'un signifie une probabilité d'erreur constante, alors ce qui précède est en effet le meilleur que je connaisse. Pour une discussion détaillée, voir Sec 2.5.2.4 dans mon livre "The Foundations of Cryptography - Volume 1" disponible sur http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html

LE CI-DESSUS EST MAUVAIS. VOIR LA RÉPONSE CORRIGÉE CI-DESSOUS.

O(nJournal3(1/ϵ))n2nΩ(ϵ2)2/3O~(n/ϵ2)

Oded Goldreich
la source
2
L'histoire (de mon erreur): En voyant cette question, j'ai juste regardé ladite section, j'ai lu la déclaration de manière erronée (en raison de la hâte), et j'ai simplement répondu sans réfléchir. Plus tard, je me suis rappelé vaguement qu'on m'avait une fois posé la même question et répondu différemment. J'ai donc vérifié plus attentivement. Leçons (que j'aurais dû savoir): Ne faites pas les choses à la hâte; n'agis pas sans penser ...
Oded Goldreich