Проект по теоретической информатике 2018

Исследовательский проект

Что за проект?

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

Правила отбора

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

Контакты

Владимир Подольский

vpodolskii@hse.ru

Возможные темы проекта

Тема проекта: Формулы для функций Шпрага-Гранди.

Ментор: Владимир Александрович Гурвич

Будет рассматриваться широкий класс комбинаторных симметричных (impartial) игр. Цель — получить явные формулы для функций Шпрага-Гранди в нормальной и мизерной версиях и выявить связь между этими версиями. Это возможно далеко не всегда. Хотелось бы найти такие формулы для широкого класса игр.

Литература

1. Winning Ways for your mathematical plays, volume 1; Elwyn Berlekamp, John H. Conway, and Richard Guy, https://annarchive.com/files/Winning%20Ways%20for%20Your%20Mathematical%20Plays%20V1.pdf

2. On the misere version of game Euclid and miserable games; Discrete Math. 307:9-10 (2007) 1199-1204; Vladimir Gurvich.

Примечания: Проект не требует от студента существенных предварительных знаний (всё необходимое будет объяснено). Однако, проект потребует существенных затрат времени. Необходим также хороший программистский уровень: умение поставить эффективный вычислительный эксперимент (алгоритмы будут подробно объяснены). Опыт показывает, что формулы для функций Шпрага-Гранди могут быть довольно сложными и, чтобы угадать такую формулу, потребуется вычислить значение функции для большого числа позиций. В октябре 2018 и 20 января - 12 мая 2019 связь по скайпу.

Тема проекта: Чувствительность булевых функций

Ментор: Михаил Николаевич Вялый

Одной из важных характеристик в анализе булевых функций является чувствительность. На самом деле существует два варианта определения чувствительности и взаимосвязь между ними до конца не прояснена. Так называемая гипотеза чувствительности (sensitivity conjecture) формулируется очень просто и остается недоказанной уже много лет. За это время выяснилось, что эта гипотеза имеет много равносильных (или более сильных) формулировок. В проекте предлагается разобраться с этими достижениями.

Литература https://theoryofcomputing.org/articles/gs004/gs004.pdf (хороший, хотя уже несколько устаревший, обзор по вариантам гипотезы чувствительности) https://arxiv.org/abs/1207.1824 (продолжение одной из тем обзора об одном из самых интересных вариантов гипотезы чувствительности) С гипотезой чувствительности связана интересная игра, про которую пока известно очень немного (поэтому есть основательная надежда получить какие-то новые результаты даже не очень сложными рассуждениями). Несколько ссылок https://iuuk.mff.cuni.cz/~koucky/LBCAD/papers/sensitivity%20game.pdf (формулировка игры и связь с гипотезой чувствительности) (верхние оценки для GKS игры) https://arxiv.org/abs/1506.06456 https://arxiv.org/abs/1712.01149

Тема проекта: Исправление ошибок в коммуникационных протоколах.

Ментор: Александр Николаевич Козачинский

Предположим A, B --- подмножества множества из n элементов такие, что |A| + |B| > n. Тогда A и B пересекаются. Пусть Алиса получает на вход A, а Боб --- B. Они хотят найти какой-нибудь элемент пересечения. Нетрудно понять, как им передать друг другу не более O(\log^2 n) битов, чтобы с этим справиться. А что если какая-то доля посылаемых битов может приходить с ошибкой? Достаточно ли и в этом случае O(\log^2 n) битов? Из общей теоремы Бравермана и Рао (применимую не только к этой задаче, а и к любой другой) вытекает, что если доля ошибок меньше 1/8, то ответ положительный. А если доля ошибок, скажем, 1/6, будет ли ответ положительным хотя бы только для этого (или для какого-нибудь другого интересного) частного случая?

Литература: Теорема Бравермана-Рао: Braverman M., Rao A. Toward coding for maximum errors in interactive communication. // IEEE Transactions on Information Theory, 2014.

Более старый, более слабый и более простой результат Шульмана: Leonard J. Schulman. Coding for interactive communication. IEEE Transactions on Information Theory, 1996

Полиномиальный алгоритм исправления ошибок в коммуникационных протокола: Zvika Brakerski and Yael Tauman Kalai. Efficient interactive coding against adversarial noise. In FOCS, pages 160–166, 2012