Home

Пятница, 14 мая, 18:00, к. 106

Пятница, 14 мая, ауд. 106. Начало в 18:00.

Докладчик: Д. Соколов.

Тема: Сложность обращения функции Голдрейха алгоритмами расщепления.

Abstract

Рассмотрим функцию $ g: \{0,1\}^n \to \{0,1\}^n $, в которой каждый бит выхода зависит от некоторых $ d $ битов входа и вычисляется по некоторому предикату (одному для всех выходов). В 2000 году Голдрейх выдвинул гипотезу, что если граф зависимости является экспандером, а предикат случайный, то такая функция является односторонней. В 2005 году Алехновичем, Гиршем и Ицыксоном была доказана экспоненциальная нижняя оценка на сложность обращения функции Голдрейха, основанной на случайном графе и линейном предикате, близорукими алгоритмами расщепления. В 2009 году Кук, Миллер, Эстами и Тревисан обобщили этот результат на нелинейный предикат. Ицыксон в 2009 году доказал нижнюю оценку на сложность обращения таких функций "пьяными" алгоритмами, основанными на расщеплении. Во всех перечисленных результатах нижняя оценка вероятностная и достигается на случайном графе. В докладе будет приведена явная конструкция функции Голдрейха, на которой достигаются все перечисленные оценки. Кроме того будет рассказано простое доказательство нижней оценки для "близоруких" алгоритмов в случае линейных предикатов. Доклад основан на совместных результатах докладчика и Д.М. Ицыксона.