Пятница, 17 декабря, ауд. 311. Начало в 18:00.
Докладчик: В. Николаенко (Академический Университет).
Тема: Оптимальный эвристический аксептор без случайных битов.
Abstract
В докладе будет доказано существование оптимального детерминированного эвристического аксептора для некоторого класса распределенных задач доказательств. Предлагаемая конструкция является дерандомизацией конструкции оптимального вероятностного эвристического аксептора Э.А. Гирша и Д.М. Ицыксона. Конструкция опирается на псевдослучайный граф с хорошими свойствами перемешивания. В докладе будет также рассказан пример такого графа, предложенный Голдрейхом и Вигдерсоном в 1994 году. Будет показано, что если существуют односторонние перестановки, то среди рассматриваемого класса распределенных задач будут и такие, для которых нет полиномиально ограниченного эвристического аксептора. Доклад основан на совместных результатах докладчика и Д.М. Ицыксона.
