Наилучшая сложность запросов алгоритма обучения Голдрайха-Левина / Кушилевица-Мансура

Какова наиболее известная сложность запроса алгоритма обучения Голдрайха-Левина? Лекционные заметки из блога Лука Тревисан в , леммы 3, утверждает его как . Это самый известный с точки зрения зависимости от п ? Буду особенно благодарен за ссылку на цитируемый источник!$O(1/\epsilon^4 n \log n)$$n$

Смежный вопрос: какова наиболее известная сложность запроса алгоритма обучения Кушилевица-Мансура?

Вопрос кажется несколько недооцененным в том смысле, что в нем не указана желаемая вероятность ошибки процедуры. Если предположить, что одно означает постоянную вероятность ошибки, то вышесказанное действительно лучшее, что я знаю Подробное обсуждение см. В разделе 2.5.2.4 моей книги «Основы криптографии - том 1», доступной по адресу: http://www.wisdom.weizmann.ac.il/~oded/foc-vol1.html.

ВЫШЕ НЕПРАВИЛЬНО. СМОТРЕТЬ ИСПРАВЛЕННЫЙ ОТВЕТ НИЖЕ.

$O(n \log^3(1/\epsilon))$$n^2$$n$$\Omega(\epsilon^2)$$2/3$${\tilde O}(n/\epsilon^2)$