Односторонняя коммуникационная сложность нахождения наибольшего общего начала.
По работе Harry Buhrman, Michal Koucky, Nikolai K. Vereshchagin. Randomised Individual Communication Complexity. IEEE Conference on Computational Complexity 2008,
PDF.
Построение генераторов сложных формул для SAT-solver'ов
10 октября 2011
Александр Рубцов
О регулярных событиях в сверхсловах
26 сентября 2011
Николай Верещагин
Понятие истинности вероятностных гипотез по Бонгарду
16 мая 2011
Григорий Ярославцев
Тестирование свойства и коммуникационная сложность
25 апреля 2011
Шаура Ишкина
Сложность разрешения четверок слов
18 апреля 2011
И.Д. Шкредов
О нормах Гауэрса
11 апреля 2011
Даниил Мусатов
Колмогоровские экстракторы с полиномиальным ограничением на сложность вычислений
продолжение
4 апреля 2011
Даниил Мусатов
Колмогоровские экстракторы с полиномиальным ограничением на сложность вычислений
28 марта 2011
Илья Разенштейн
Извлекаемость общей информации из случайной пары близких строк
продолжение
21 марта 2011
Илья Разенштейн
Извлекаемость общей информации из случайной пары близких строк
14 марта 2011
Н.К.Верещагин
Проблема Какея и merger Двира и Вигдерсона
21 февраля 2011
И. Разенштейн
Экстрактор Бургейна
продолжение
14 февраля 2011
И. Разенштейн
Экстрактор Бургейна
2010
6 декабря 2010
Андрей Ромащенко
Об экономном хранении множеств
29 ноября 2010
Александр Шень
Парадокс неожиданной контрольной, колмогоровская сложность и вторая теорема Гёделя" (по недавней работе Shira Kritchman, Ran Raz).
22 ноября 2010
Андрей Румянцев
О конструктивном варианте локальной леммы Ловаса
продолжение
15 ноября 2010
Андрей Румянцев
О конструктивном варианте локальной леммы Ловаса
1 ноября 2010
Илья Разенштейн
О PCP теореме
продолжение
25 октября 2010
Илья Разенштейн
О PCP теореме
11 октября 2010
Даниил Мусатов
Эффективизация теорем о колмогоровской сложности при помощи генератора Нисана-Вигдерсона
продолжение
4 октября 2010
Александр Шерстов (Microsoft Research, New England)
Методы двойственности в теории коммуникационной сложности
27 сентября 2010
Даниил Мусатов
Эффективизация теорем о колмогоровской сложности при помощи генератора Нисана-Вигдерсона
6 сентября 2010
На первом заседании будет обсуждаться план работы семинара на 2010-2011 учебный год и возможные задачи (в том числе для курсовых и дипломных работ).
26 апреля 2010
Максим Бабенко
Выделение почти регулярных подграфов в почти регулярных графах
19 апреля 2010
Антон Махлин
Алгебризуемость
продолжение
12 апреля 2010
Антон Махлин
Алгебризуемость (по работе С.Ааронсона и А.Вигдерсона)
5 апреля 2010
И.Разенштейн и М.Андреев
Области определения оптимальных декомпрессоров
29 марта 2010
Михаила Вялого
Орбиты линейных отображений и свойства регулярных языков
22 марта 2010
Петр Митричев
Об извлечении полезной информации
15 марта 2010
М.Е. Жуковский
Количество расширений подграфов в случайном графе. Законы нуля или единицы для свойств случайных графов
2009
14 декабря 2009
Н.К.Верещагин
Алгоритмические достаточные статистики
7 декабря 2009
Михаил Раскин
Виртуальная файловая система, основанная на понятии запроса
30 ноября 2009
Н.П. Варновский
Криптографические протоколы голосования
23 ноября 2009
Лмитрий Скопинцев
Явная конструкция оптимального экстрактора (По работе V. Guruswami, S. Vadhan, C. Umans.
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.)
продолжение
16 ноября 2009
Лмитрий Скопинцев
Явная конструкция оптимального экстрактора (По работе V. Guruswami, S. Vadhan, C. Umans.
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.)
2 ноября 2009
Александр Шень
Множества k-независимых слов в алгоритмической теории информации
19 октября 2009
О префиксной сложности задачи преобразования любого объекта из данного конечного множества в данный объект
5 октября 2009
Даниил Мусатов
Алгоритм Ароры приближенного решения задачи коммивояжера для графов на плоскости
продолжение
28 сентября 2009
Даниил Мусатов
Алгоритм Ароры приближенного решения задачи коммивояжера для графов на плоскости
21 сентября 2009
Михал Коуцки (Michal Koucky, Институт математики академии наук Чехии, Прага)
How to Explore a Fast-Changing World: Cover Time of a Simple Random Walk on Evolving Graphs
18 мая 2009
Владимир Подольский
Полилогарифмическая независимость обманывает схемы ограниченной глубины
4 мая 2009
студенты 5 курса расскажут о своих дипломных работах
27 апреля 2009
Г.А.Кучерова (российско-французская Лаборатория Понселе)