Пятница, 14 мая, ауд. 106. Начало в 18:00.
Докладчик: Д. Соколов.
Тема: Сложность обращения функции Голдрейха алгоритмами расщепления.
Abstract
Рассмотрим функцию
, в которой каждый бит выхода зависит от некоторых
битов входа и вычисляется по некоторому предикату (одному для всех выходов). В 2000 году Голдрейх выдвинул гипотезу, что если граф зависимости является экспандером, а предикат случайный, то такая функция является односторонней. В 2005 году Алехновичем, Гиршем и Ицыксоном была доказана экспоненциальная нижняя оценка на сложность обращения функции Голдрейха, основанной на случайном графе и линейном предикате, близорукими алгоритмами расщепления. В 2009 году Кук, Миллер, Эстами и Тревисан обобщили этот результат на нелинейный предикат. Ицыксон в 2009 году доказал нижнюю оценку на сложность обращения таких функций "пьяными" алгоритмами, основанными на расщеплении. Во всех перечисленных результатах нижняя оценка вероятностная и достигается на случайном графе. В докладе будет приведена явная конструкция функции Голдрейха, на которой достигаются все перечисленные оценки. Кроме того будет рассказано простое доказательство нижней оценки для "близоруких" алгоритмов в случае линейных предикатов. Доклад основан на совместных результатах докладчика и Д.М. Ицыксона.