Долгое время считалось, что алгоритм с линейным временем работы является естественным пределом мечтаний для любой нетривиальной вычислительной задачи. Действительно, сложно представить ситуацию, когда алгоритм не должен читать весь свой вход для ответа на поставленную задачу. Однако, современный мир и растущие объемы данных ставят более амбициозные цели: решить задачу, прочитав лишь малую долю входа. Для некоторых задач известны точные алгоритмы с сублинейным временем работы, но зачастую для естественных задач алгоритмам требуется использовать случайные биты для в некотором смысле приближенного ответа на задачу. Данная область активно развивается, и границы таких алгоритмов пока остаются размытыми. Для создания сублинейных алгоритмов используется множество интересных комбинаторных и алгебраических техник. Для многих задач найдены оптимальные алгоритмы (в некоторых гарантиях), но ещё больше остается открытых задач как в доказательстве нижних оценок, так и в улучшении верхних оценок. Область связана со многими разделами теоретической информатики: коды исправляющие ошибки, потоковые алгоритмы, коммуникационная сложность, приближенные алгоритмы, вероятностно проверяемые доказательства.

В течение семинара планируется разобрать техники и основные результаты в данной области, полученные за последние годы. Формат семинара предполагает еженедельные доклады и обсуждение материала, доклады будут делаться студентами-участниками семинара. Предполагается, что участники будут знакомы с дискретной теорией вероятностей и базовым курсом алгоритмов.

Руководитель семинара: Николай Карпов.