Проект по теоретической информатике 2018 — различия между версиями
| Строка 5: | Строка 5: | ||
Проект по теоретической информатике является научным исследованием в области теоретического Computer Science. Проект предназначен для тех, кто всерьез рассматривает для себя возможность заниматься в будущем теоретическими исследованиями. | Проект по теоретической информатике является научным исследованием в области теоретического Computer Science. Проект предназначен для тех, кто всерьез рассматривает для себя возможность заниматься в будущем теоретическими исследованиями. | ||
| + | == Правила отбора == | ||
| + | |||
| + | Отбор на проект по теоретической информатике производится по результатам собеседования. На собеседовании проверяется владение студентом знаниями и навыками, достаточными для успешной работы по выбранной теме, а также мотивация студента. В частности, в рамках описания мотивации от студента ожидаются примеры того, что он уже делал ранее, подтверждающие его интерес к теоретическим исследованиям (это может быть посещение факультатива, прохождение соответствующей летней практики, самостоятельное изучение какой-то области и т.д.). | ||
== Контакты == | == Контакты == | ||
| Строка 11: | Строка 14: | ||
vpodolskii@hse.ru | 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 | ||
Версия 02:19, 9 октября 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
