City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Hardness vs Randomness
Saint Petersburg / spring 2009, посмотреть все семестры

Enroll in the course to get notifications and to be able to submit home assignments.
Register to enroll now Login

Представим себе, что есть явная вычислительная задача, про которую достоверно известно, что ее нельзя решить за разумное время. Хорошо это или плохо? С одной стороны, грустно, наверное, мы никогда не сможем решать эту задачу. С другой стороны, не только мы, но и враг не сможет решить эту задачу за разумное время и можно попытаться использовать это задачу для надежного шифрования данных, чтобы враг не смог взломать шифр, не решив задачу. Это идея появилась давно и попытки строить криптографические протоколы на основе вычислительно трудных задач начались в 1970–х годах.

Другая неожиданная польза от вычислительно трудных задач была открыта в конце 1990–х — начале 2000–х. И этот результат является одним из самых ярких результатов в теоретической информатики последних лет (и является основным в этом курсе). Оказывается, имея явную вычислительно трудную задачу, можно избавиться от случайных чисел в вероятностных алгоритмах. Ситуация в мире вычислений такая: либо любой вероятностный алгоритм можно дерандомизировать избавиться от использования случайных чисел), либо не существуют явных вычислительно сложных задач.

Под явной задачей имеется в виду задача, которую можно решить за экспоненциальное время, а под вычислительно трудной — такая, которая не решается с помощью булевых схем полиномиального размера. Хотя случайная булевая функция с большой вероятностью решается только схемами экспоненциального размера, ни для какой явной функции мы доказывать это не умеем. Курс начнется с самых красивых примеров экспоненциальных нижних оценок в ограниченных (в неограниченных же не получается!!) моделях вычислений: монотонные схемы (за этот результат А. Разборов получил премию Неванлинны), схемы ограниченной глубины и др. Продемонстрировав существующую технику доказательств нижних оценок, мы поговорим о философской и полемической работе А. Разборова и С. Рудича “Natural proofs” (авторы удостоились премии Гёделя в 2007–м году за этот результат), основной результат которой заключается в том, что существующая техника оказательства нижних оценок является «естественной», а при разумных криптографических предположениях, естественных доказательств недостаточно для того, чтобы доказать нетривиальную нижнюю оценку для схем.

Вторая часть курса будет посвящена непосредственно дерандомизации (избавлению алгоритмов от случайных чисел). Будут приведены результаты о том, как можно понижать вероятность ошибки алгоритма, используя лишь небольшое число дополнительных случайных битов, будет рассказан детерминированный (дерандомизация вероятностного) алгоритм Рейнгольда выхода из лабиринта, использующий только логарифмическую (от размера лабиринта) память, будут приведены конструкции экстракторов, графские конструкции, позволяющие использовать «плохие» (зависимые, неравномерно распределенные) случайные биты в алгоритмах. И главным результатом этой части будет дерандомизация при условии cуществования функции, вычислимой за экспоненциальное время, которая не вычислима с помощью схем полиномиального размера.

В доказательствах основных результатов курса будет использоваться и подробно обсуждаться глубокая современная техника: random restriction lemma, error–correcting codes, Impagliazzo hardcore lemma, Yao XOR lemma, графы–расширители и пр. Понимание этой техники может существенно облегчить чтение статей по теоретической информатики. Курс может рассматриваться, как продолжение курса «Структурная теория сложности», но не будет от него зависеть, все нужные определения будут повторены. Несмотря на амбициозность программы курса, курс планируется читать достаточно подробно и понятно, так что на него приглашаются и слушатели, которые раньше не сталкивались с этой областью.

Date and time Class|Name Venue|short Materials
15 February
10:10–11:40
Теорема Разборова о нижней оценке на сложность монотонных схем, Lecture ПОМИ РАН slides
22 February
10:10–11:40
Нижние оценки для схем ограниченной глубины, Lecture ПОМИ РАН slides
15 March
10:10–11:40
Еще одна нижняя оценка для схем ограниченной глубины (теорема Разборова–Смоленского), Lecture ПОМИ РАН slides
15 March
11:50–13:20
Естественные доказательства (natural proofs), Lecture ПОМИ РАН slides
22 March
10:20–11:50
Псевдослучайный генератор Нисана–Вигдерсона, Lecture ПОМИ РАН slides
12 April
10:20–11:50
Повышение трудности функций: лемма Импальяццо о трудном распределении, XOR лемма Яо, Lecture ПОМИ РАН slides
12 April
12:00–13:30
Псевдослучайный генератор Нисана–Вигдерсона (окончание). Конструкция дизайна, Lecture ПОМИ РАН slides
19 April
10:20–11:50
Повышение трудности функций: коды, исправляющие ошибки. Коды Рида–Соломона, Уолша–Адамара, Рида–Мюллера. Локальное декодирование, Lecture ПОМИ РАН slides
26 April
10:25–11:55
Уменьшение вероятности ошибки с помощью блуждания по экспандеру, Lecture ПОМИ РАН slides
03 May
10:25–11:55
Экстракторы: существование, конструкция из случайного блуждания по экспандеру, Lecture ПОМИ РАН slides
10 May
10:25–11:55
Дерандомизация вычислений с логарифмической памятью, Lecture ПОМИ РАН slides
10 May
12:00–13:30
Экстрактор из псевдослучайного генератора, Lecture ПОМИ РАН slides