Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 03/2009

НИЖНЯЯ ОЦЕНКА НА СРЕДНЕЕ ВРЕМЯ ОБРАЩЕНИЯ ФУНКЦИИ ГОЛДРЕЙХА "ПЬЯНЫМИ" АЛГОРИТМАМИ РАСЩЕПЛЕНИЯ

This preprint was accepted July 17, 2009

АННОТАЦИЯ:
Мы доказываем экспоненциальную нижнюю оценку на среднее время обращения
функции Голдрейха [Gol00] "пьяными" [AHI05] алгоритмами,
тем самым разрешаем открытый вопрос, поставленный в работе [CEMT09]. 
Функция Голдрейха, которую мы используем задана графом-расширителем 
и предикатом $P_d(x_1,x_2,\dots, x_d)=
x_1\oplus x_2\oplus\dots \oplus x_{d-k}\oplus Q(x_{d-k+1},\dots, x_d)$,
где $Q$ --- произвольный $k$-местный предикат, $k+1<\frac{d}{4}$. 
"Пьяные" алгоритмы --- это семейство алгоритмов, основанных
на расщеплении, которые используют ничем не ограниченную эвристику
выбора переменной для расщепления, а значение, которое подставляется
первым, выбирается случайным образом.
Техника доказательства существенно упрощает технику, используемую
в [AHI05] и [CEMT09].