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

Ментор	Подольский Владимир Владимирович
Учебный семестр	Осень 2018
Учебный курс	2-й курс
Максимальное количество студентов, выбравших проект: 30

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

Проект по теоретической информатике является научным исследованием в области теоретического 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

Тема проекта: Вычисление булевых функций многочленами.

Ментор: Владимир Владимирович Подольский

Вычисление булевых функций многочленами рассматривается в области сложности вычислений в связи с тем, что эта модель помогает доказывать нижние оценки для ряда других вычислительных моделей, например, для булевых схем и разрешающих деревьев. Есть несколько разных моделей вычисления функций многочленами, например, точные и приближенные вычисления над действительными числами, вычисления по модулю, пороговые функции. Предлагается изучить некоторые из этих моделей и взаимосвязи между ними. Чтобы больше узнать об этой области можно посмотреть обзор by Richard Beigel http://knight.cis.temple.edu/~beigel/papers/polynomial-survey-structures.html

Тема проекта: Пороговые функции и пороговые схемы.

Ментор: Владимир Владимирович Подольский

Пороговые функции – это булевы функции, определяемые следующим образом. Пусть дан целочисленный многочлен (часто линейный) от n переменных. Подставим вместо его переменных входы булевой функции и вычислим его значение над целыми числами. Если результат больше нуля, то выход функции полагаем равным 1, иначе полагаем функцию равной 0. Пороговые функции и булевы схемы, составленные из пороговых функций, являются важными моделями в теоретической информатике. Немного больше об этом можно узнать в обзоре by Richard Beigel http://knight.cis.temple.edu/~beigel/papers/polynomial-survey-structures.html

Тема проекта: Сложность булевых схем.

Ментор: Владимир Владимирович Подольский

Булевы схемы – одна из основных вычислительных моделей в теории сложности вычислений. Основной интерес к ней связан с доказательством нижних оценок сложности вычислений. Это большая тема и в ней можно либо изучить основы, либо подробно разобраться в каком-то конкретном направлении. Из доступных в Интернете источников в этой области можно посмотреть книгу by Ingo Wegener http://eccc.hpi-web.de/resources/pdf/cobf.pdf. Также на эту тему есть свежая книга “Boolean Function Complexity”, Stasys Jukna.

Тема проекта: Коммуникационная сложность и ее приложения.

Ментор: Владимир Владимирович Подольский

Типичная задача коммуникационной сложности выглядит так. Есть два человека, которые хотят вычислить функцию f(x,y) на какой-то паре входов (x,y). При этом первый знает только x, а второй только y, то есть чтобы вычислить функцию им нужно обмениваться информацией. Какое минимальное количество информации им нужно передать друг другу, чтобы вычислить функцию? Например, x и y могут быть файлами, и участники вычисления хотят узнать, совпадают ли эти файлы. Коммуникационная сложность оказывается очень полезной при доказательстве нижних оценок сложности вычислений в множестве вычислительных моделей. Подробнее об этом можно почитать в обзоре by Eyal Kushilevitz http://www.cs.technion.ac.il/~eyalk/cc-survey.ps.Z