Post #109
906
Большинство высказалось за спецкурс по псевдослучайности. Присоединяйтесь к чату, оставшемуся от прошлого года: https://t.me/joinchat/DZlFTRI3Dvope1VxBqmUng
Channel Public Channel
СЛ Сложность вычислений ФПМИ
@diht_complexity
Новости курса "Сложность вычислений" для 3 курса ФИВТ МФТИ
- Subscribers
- 1.1K
- Photos
- 12
- Videos
- 0
- Links
- 160
Showing posts older than #110 · Back to latest
Older Posts 20 shown
Post #108
74
Forwarded from Сложность вычислений ФПМИ via @catgroupagreebot
📊 Традиционно осенью я читаю продвинутый спецкурс для узкой аудитории по тематике, связанной со сложностью вычислений. На что вам было бы интересно ходить? (Можно выбрать несколько вариантов).
Вероятностно проверяемые доказательства (PCP-теорема с полным доказательством, unique game conjecture, приближения для конкретных задач) [2]
├ Nikita Sveshnikov
└ Yan Slabodich
Псевдослучайность и дерандомизация (экспандеры, экстракторы, генераторы псевдослучайных чисел и связи между ними. Почему мы думаем, что BPP=P) [4]
├ Yan Slabodich
├ Ruslan Ishmukhametov
├ Илья Курузов
└ Andrei Asanau
Тотальные задачи поиска и теоремы о неподвижных точках (подробно про класс PPAD и прочие, связи с теорией игр, экономическими равновесиями и топологией) [1]
└ Matvey Bezlepkin
Рациональные интерактивные доказательства (обзор моделей, в том числе с несколькими Мерлинами и различными способами взаимодействия между ними) [2]
├ Yan Slabodich
└ Matvey Bezlepkin
👥 6 людей проголосовали
Вероятностно проверяемые доказательства (PCP-теорема с полным доказательством, unique game conjecture, приближения для конкретных задач) [2]
├ Nikita Sveshnikov
└ Yan Slabodich
Псевдослучайность и дерандомизация (экспандеры, экстракторы, генераторы псевдослучайных чисел и связи между ними. Почему мы думаем, что BPP=P) [4]
├ Yan Slabodich
├ Ruslan Ishmukhametov
├ Илья Курузов
└ Andrei Asanau
Тотальные задачи поиска и теоремы о неподвижных точках (подробно про класс PPAD и прочие, связи с теорией игр, экономическими равновесиями и топологией) [1]
└ Matvey Bezlepkin
Рациональные интерактивные доказательства (обзор моделей, в том числе с несколькими Мерлинами и различными способами взаимодействия между ними) [2]
├ Yan Slabodich
└ Matvey Bezlepkin
👥 6 людей проголосовали
Post #107
651
Напоминаю про опрос о спецкурсе. Если кто ещё хочет высказаться, прошу. Начальство уже хочет определённости.
Post #106
687
Сложность вычислений ФПМИ Контрольная работа проверена. Результаты по ссылке: https://docs.google.com/spreadsheets/d/1p9YwRr7l-mxoNcjfF7wIS37ukwO6egrC9aRDdqDXu6I/edit?usp=sharing Работы можно будет посмотреть завтра в 117 ГК, ориентировочно с 11 до 15 (там будет экзамен по ДА). Домашка…
К сожалению, работы только с часа можно будет посмотреть
Post #105
706
Контрольная работа проверена. Результаты по ссылке: https://docs.google.com/spreadsheets/d/1p9YwRr7l-mxoNcjfF7wIS37ukwO6egrC9aRDdqDXu6I/edit?usp=sharing Работы можно будет посмотреть завтра в 117 ГК, ориентировочно с 11 до 15 (там будет экзамен по ДА). Домашка пока не проверена и в ближайшие дни вряд ли будет.
Google Docs ФИВТ: Сложность вычислений: дополнительные главы, весна 2019 Sheet1
контрольная,домашка
студент,1,2,3,4,5,6,7,8,9,сумма,1,2,3,4,5,6,7,8,9
Анисимова Виктория,1,5,0,0,0,14,0,2,15,37,8,0,0,10,0,7,7,7,0
Асанов Андрей,0,0,5,2,4,15,4,0,15,45,8,10,0,10,10,7,8,10,0
Безлепкин Матвей,1,3,5,0,2,10,0,2,15,38,10,8,5,10,9,8,10… Post #104
748
Контрольная работа состоится в среду, 29 мая, с 12 до 14 в ауд. Гарвард. Она пройдёт вместе с к/р по алгоритмической теории игр у первого курса магистратуры.
Post #103
783
derandomization-program.pdf137.1 KB
Примерная программа спецкурса про дерандомизацию. Другие два я пока ни разу не читал, так что и программ нет.
Post #102
727
PCP-program-2017.pdf113.7 KB
Примерная программа спецкурса по PCP
Post #101
1.27K
📊 Традиционно осенью я читаю продвинутый спецкурс для узкой аудитории по тематике, связанной со сложностью вычислений. На что вам было бы интересно ходить? (Можно выбрать несколько вариантов).
Вероятностно проверяемые доказательства (PCP-теорема с полным доказательством, unique game conjecture, приближения для конкретных задач) [2]
├ Nikita Sveshnikov
└ Yan Slabodich
Псевдослучайность и дерандомизация (экспандеры, экстракторы, генераторы псевдослучайных чисел и связи между ними. Почему мы думаем, что BPP=P) [4]
├ Yan Slabodich
├ Ruslan Ishmukhametov
├ Илья Курузов
└ Andrei Asanau
Тотальные задачи поиска и теоремы о неподвижных точках (подробно про класс PPAD и прочие, связи с теорией игр, экономическими равновесиями и топологией) [1]
└ Matvey Bezlepkin
Рациональные интерактивные доказательства (обзор моделей, в том числе с несколькими Мерлинами и различными способами взаимодействия между ними) [2]
├ Yan Slabodich
└ Matvey Bezlepkin
👥 6 людей проголосовали
Вероятностно проверяемые доказательства (PCP-теорема с полным доказательством, unique game conjecture, приближения для конкретных задач) [2]
├ Nikita Sveshnikov
└ Yan Slabodich
Псевдослучайность и дерандомизация (экспандеры, экстракторы, генераторы псевдослучайных чисел и связи между ними. Почему мы думаем, что BPP=P) [4]
├ Yan Slabodich
├ Ruslan Ishmukhametov
├ Илья Курузов
└ Andrei Asanau
Тотальные задачи поиска и теоремы о неподвижных точках (подробно про класс PPAD и прочие, связи с теорией игр, экономическими равновесиями и топологией) [1]
└ Matvey Bezlepkin
Рациональные интерактивные доказательства (обзор моделей, в том числе с несколькими Мерлинами и различными способами взаимодействия между ними) [2]
├ Yan Slabodich
└ Matvey Bezlepkin
👥 6 людей проголосовали
Post #100
556
shen-miprus.pdf200.2 KB
Конспект Шеня про MIP=NEXP, по которому я читал лекцию вчера
Post #99
565
compl-topics-hw-2019.pdf227.8 KB
Домашнее задание с исправленной ошибкой в 9-й задаче
Post #98
851
compl-book-no-answers.pdf2.9 MB
Актуальная версия книги без ответов на задачи (т.к. некоторые даны в качестве домашки). Изменения небольшие - исправлены некоторые ошибки, появилось несколько новых разделов. Некоторые главы пока по-прежнему обрываются на полуслове, работа продолжается.
Post #97
631
Сложность вычислений ФПМИ Голосование давайте закончим 30 апреля в 19 часов. Если к тому времени не наберётся трёх желающих, то занятия не будет.
Поскольку 3 желающих так и не набралось, занятия 2 мая не будет. Остаётся одно занятие 16-го, принимаются пожелания по его теме и сроку к/р.
Post #96
620
compl-topics-hw-2019.pdf227.7 KB
Домашние задачи, отвечающие за половину оценки. Сроки пока не установлены. Если будет лекция 2 мая, возможно добавление ещё одной задачи.
Post #95
563
Сложность вычислений ФПМИ 📊 Придёте ли вы на занятие 2 мая, если оно будет? (Занятие состоится, если будет хотя бы трое желающих, тема не войдёт в к/р, но войдёт в домашку). Да [2] ‎├ Darya Lapa ‎└ Yan Slabodich Нет [7] ‎├ Artem Sapozhnikov ‎├ Viacheslav Ivanov ‎├ Aleksandr Grishutin…
Голосование давайте закончим 30 апреля в 19 часов. Если к тому времени не наберётся трёх желающих, то занятия не будет.
Post #94
587
📊 Придёте ли вы на занятие 2 мая, если оно будет? (Занятие состоится, если будет хотя бы трое желающих, тема не войдёт в к/р, но войдёт в домашку).
Да [2]
├ Darya Lapa
└ Yan Slabodich
Нет [7]
├ Artem Sapozhnikov
├ Viacheslav Ivanov
├ Aleksandr Grishutin
├ Илья Курузов
├ Дмитрий Невструев
├ Ruslan Ishmukhametov
└ Victoria Anisimova
Не знаю [3]
├ Egor
├ Максим
└ Nikita Mikhaylov
👥 10-15 людей проголосовали
Да [2]
├ Darya Lapa
└ Yan Slabodich
Нет [7]
├ Artem Sapozhnikov
├ Viacheslav Ivanov
├ Aleksandr Grishutin
├ Илья Курузов
├ Дмитрий Невструев
├ Ruslan Ishmukhametov
└ Victoria Anisimova
Не знаю [3]
├ Egor
├ Максим
└ Nikita Mikhaylov
👥 10-15 людей проголосовали
Post #93
546
Сегодня топологии всё ещё не будет, сложность будет примерно до 3 часов. В следующий раз, 25 апреля, не будет сложности и, вероятно, будет две топологии.
Post #92
580
Musatov-PPAD-general.pdf1.3 MB
В четверг начали изучать классы задач поиска по приложенной презентации. На этой неделе продолжим.
Post #91
618
Сложность вычислений ФПМИ Сегодня занятия по допглавам начнутся с опозданием, ориентировочно в 12:30. Продолжим изучать рациональные интерактивные доказательства.
А Глеб Гусев заболел, так что топологии, наоборот, не будет. Возможно, моя лекция будет подольше - обсудим, как я подойду.
Post #90
572
Сегодня занятия по допглавам начнутся с опозданием, ориентировочно в 12:30. Продолжим изучать рациональные интерактивные доказательства.