Laboratory of Mathematical Logic at PDMI

Пятница, 20 сентября, комната 106. Начало в 16:00.

Докладчик: А. А. Кожевников.

Доклад по статье: M.Alekhnovich, E.Ben-Sasson
ANALYSIS OF THE RANDOM WALK ALGORITHM ON RANDOM 3-CNFS
В статье исследуется поведение простейшего алгоритма случайного блуждания на случайно порожденных формулах. В частности, доказывается верхняя полиномиальная оценка для случая формул с плотностью (=кол-во дизъюнкций/кол-во переменных) менее 1.63 и нижняя экспоненциальная оценка для случая с большой плотностью.