Post #452
2.41K
Семинар 08. Класс PH.pdf161.5 KB
Задачи к 8-му семинару
Channel Public Channel
СЛ Сложность вычислений ФПМИ
@diht_complexity
Новости курса "Сложность вычислений" для 3 курса ФИВТ МФТИ
- Subscribers
- 1.11K
- Photos
- 12
- Videos
- 0
- Links
- 160
Showing posts older than #453 · Back to latest
Older Posts 18 shown
Post #451
1.65K
Forwarded from Кроссворд Тьюринга (Ваня Яковлев)
📢 Лекция Льва Суханова в это воскресенье, 22 октября, в 17:00
Лев Суханов - выпускник матфака ВШЭ и исследователь в PSE, Ethereum Foundation. Он расскажет про очень важную область криптографии, в которой он работает - быстрые проверки доказательств.
🔍 Верифицируемые вычисления при помощи sumcheck-протокола
📝
⏰ Начало в 17:00 МСК. Обратите внимание на необычное время!!!
📌 Ссылка на зум. Чтобы получать наши анонсы, зарегистрируйтесь в боте (инструкция).
#открытые_лекции #анонс
Лев Суханов - выпускник матфака ВШЭ и исследователь в PSE, Ethereum Foundation. Он расскажет про очень важную область криптографии, в которой он работает - быстрые проверки доказательств.
🔍 Верифицируемые вычисления при помощи sumcheck-протокола
📝
Давайте рассмотрим следующую ситуацию: Алиса посчитала на известных публичных данных X функцию f(X), и хочет убедить Боба в том, что ответ, который она говорит - правильный. Боб, однако, ограничен в вычислительных ресурсах, и не хочет повторять всё вычисление Алисы.
Выясняется, что (при условии что Боб допускает небольшую вероятность ошибки, скажем $2^{-128}$), такую задачу можно решить намного быстрее. Такую постановку вопроса называют "снарк" (succinct non-interactive arguments of knowledge).
Я расскажу про довольно старый протокол из 90х - sumcheck (проверка суммы), в последние год-два получивший второе дыхание в контексте делегированных вычислений и блокчейна, и построенный на этом аргументе протокол GKR (Голдвассер-Калаи-Ротблюма).
Пререквизиты: знать что такое конечное поле и уметь раскрывать скобки, если дойдём до приложений то ещё понадобится (наверное) знать что такое хэш⏰ Начало в 17:00 МСК. Обратите внимание на необычное время!!!
📌 Ссылка на зум. Чтобы получать наши анонсы, зарегистрируйтесь в боте (инструкция).
#открытые_лекции #анонс
Post #450
1.83K
Завтра в 17:00 будет открытая онлайн-лекция по одной из "горячих" тем современной сложности вычислений - верификации вычислений с использованием небольших вычислительных ресурсов. Анонс и ссылка на зум в посте ниже. Присоединяйтесь!
Post #449
2.35K
Семинар 07. Диагонализация.pdf178.5 KB
Задачи к 7-му семинару
Post #448
2.32K
Семинар_06_Самосводимости_и_пэддинг.pdf141.7 KB
Задачи к 6-му семинару
Post #447
3K
compl-2023-projects.pdf405.8 KB
Предлагаемый список проектов на этот год и правила оценивания. Сроки написаны в файле, будут уточнены после появления расписания сессии.
Записаться на выбранный проект можно в табличке https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing на листе "Проекты" (столбец C и при необходимости D напротив своего имени). Важно: на один проект можно записываться не более чем 2 людям с курса и не более чем 1 человеку из группы. На листе это проверяется. По некоторым темам возможны разные спецификации, тогда укажите свою в столбце D, критерии по повторам будут относится к конкретным спецификациям и проверяться вручную. Если выбираете тему не из файла, впишите номер 0 и название темы.
Записаться на выбранный проект можно в табличке https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing на листе "Проекты" (столбец C и при необходимости D напротив своего имени). Важно: на один проект можно записываться не более чем 2 людям с курса и не более чем 1 человеку из группы. На листе это проверяется. По некоторым темам возможны разные спецификации, тогда укажите свою в столбце D, критерии по повторам будут относится к конкретным спецификациям и проверяться вручную. Если выбираете тему не из файла, впишите номер 0 и название темы.
Сложность вычислений ФПМИ pinned «Закреплённый пост со служебной информацией, осень 2023 Расписание: Лекции - среда, 13:55-15:20, 115 КПМ (Мусатов Д.В,) Семинары по группам: 122 - вторник, 15:30-16:55, 424 Арктика (Васильчишин С.М.) 123 - среда, 10:45-12:10, 507а ГК (Ковалев К.А.) 124 - вторник…»
Post #445
2.5K
Закреплённый пост со служебной информацией, осень 2023
Расписание:
Лекции - среда, 13:55-15:20, 115 КПМ (Мусатов Д.В,)
Семинары по группам:
122 - вторник, 15:30-16:55, 424 Арктика (Васильчишин С.М.)
123 - среда, 10:45-12:10, 507а ГК (Ковалев К.А.)
124 - вторник, 10:45-12:10, 432 ГК (Коротков М.С.)
125 - среда, 9:00-10:25, 424 Арктика (Киселёв Ф.А.)
126 - понедельник, 15:30-16:55, 532 ГК (Степанов И.Д.)
127 - среда, 12:20-13:45, 512 ГК (Оверчук А.Д.)
128 - понедельник, 15:30-16:55, 532 ГК (Степанов И.Д.)
129 - вторник, 13:55-15:20, 426 ГК (Смирнов И.Н.)
151 - среда, 9:00-10:25, 514 ГК (Оверчук А.Д.)
152 - четверг, 12:20-13:45, 522 ГК (Шиманогов И.Н.)
Ресурсы для студентов:
https://t.me/diht_complexity - этот канал
https://t.me/+_zvpm0_mwVwwZThi - чат к каналу
https://www.dropbox.com/sh/6u1h2glyhucbbeg/AADLzweWSsROxmSJw7HnOXnVa?dl=0 - папка с материалами
https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing - табличка с оценками
Telegram Сложность вычислений ФПМИ Новости курса "Сложность вычислений" для 3 курса ФИВТ МФТИ Расписание:
Лекции - среда, 13:55-15:20, 115 КПМ (Мусатов Д.В,)
Семинары по группам:
122 - вторник, 15:30-16:55, 424 Арктика (Васильчишин С.М.)
123 - среда, 10:45-12:10, 507а ГК (Ковалев К.А.)
124 - вторник, 10:45-12:10, 432 ГК (Коротков М.С.)
125 - среда, 9:00-10:25, 424 Арктика (Киселёв Ф.А.)
126 - понедельник, 15:30-16:55, 532 ГК (Степанов И.Д.)
127 - среда, 12:20-13:45, 512 ГК (Оверчук А.Д.)
128 - понедельник, 15:30-16:55, 532 ГК (Степанов И.Д.)
129 - вторник, 13:55-15:20, 426 ГК (Смирнов И.Н.)
151 - среда, 9:00-10:25, 514 ГК (Оверчук А.Д.)
152 - четверг, 12:20-13:45, 522 ГК (Шиманогов И.Н.)
Ресурсы для студентов:
https://t.me/diht_complexity - этот канал
https://t.me/+_zvpm0_mwVwwZThi - чат к каналу
https://www.dropbox.com/sh/6u1h2glyhucbbeg/AADLzweWSsROxmSJw7HnOXnVa?dl=0 - папка с материалами
https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing - табличка с оценками
Post #444
1.79K
Рассадка на сегодня. Напоминаю, это Актовый зал ЛК. Места нумеруются слева направо, если смотреть на доску. Места с 1 до 7 слева от прохода, с 8 до 14 справа.
Post #443
1.88K
Организационные моменты по завтрашней контрольной:
* Контрольная будет в 13:55 в Актовом зале, рассадка будет готова утром. Продолжительность 1 час 20 минут, так что не опаздывайте к началу.
* Проверьте, что вы есть в табличке в той группе, с которой ходите на семинары: https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing. Если нет, то пишите, исправлю
* Если не можете прийти по уважительной причине, пишите до начала контрольной, лучше не впритык, чтобы мы не печатали лишних вариантов. Тогда можно будет дорешивать задачи исходя из 8 баллов за задачу, а не из 5
* Вам будет дано 2 подписанных листа: один с условиями задач и один пустой. Писать можно на обоих. Если понадобятся дополнительные листы, их можно будет взять у проводящих.
* Завтра вечером появится список проектов и форма для их выбора. Надеюсь, список студентов к тому времени устаканится.
Google Docs Сложность вычислений, осень 2023 * Контрольная будет в 13:55 в Актовом зале, рассадка будет готова утром. Продолжительность 1 час 20 минут, так что не опаздывайте к началу.
* Проверьте, что вы есть в табличке в той группе, с которой ходите на семинары: https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing. Если нет, то пишите, исправлю
* Если не можете прийти по уважительной причине, пишите до начала контрольной, лучше не впритык, чтобы мы не печатали лишних вариантов. Тогда можно будет дорешивать задачи исходя из 8 баллов за задачу, а не из 5
* Вам будет дано 2 подписанных листа: один с условиями задач и один пустой. Писать можно на обоих. Если понадобятся дополнительные листы, их можно будет взять у проводящих.
* Завтра вечером появится список проектов и форма для их выбора. Надеюсь, список студентов к тому времени устаканится.
Post #442
1.59K
Post #441
1.66K
Также сделана табличка для внесения оценок: https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing
Там не учтены переходы из группы в группу, а также студенты магистратуры блокчейн и прочие люди с других курсов. Пишите мне в личку, кого нужно перенести или добавить.
Google Docs Сложность вычислений, осень 2023 Там не учтены переходы из группы в группу, а также студенты магистратуры блокчейн и прочие люди с других курсов. Пишите мне в личку, кого нужно перенести или добавить.
Post #440
1.62K
compl-2023-test-1-training.pdf139.7 KB
В следующую среду, 11 октября, вместо лекции в 13:55 будет контрольная работа. Она пройдёт в Актовом зале. Прилагается файл с тренировочным вариантом и правилами к/р. Задачи даны с запасом, отличным результатом будет считаться 4 решённые задачи из 6, хотя могут быть и 1-2 работы со всеми решёнными. Если пропускаете по уважительной причине, пишите мне до начала контрольной.
Post #439
1.75K
Семинар 04. NP-полные языки (2).pdf119 KB
Задачи к 4-му семинару
Post #436
2.24K
Post #435
2.17K
Выкладываю листочки с задачами прошедших семинаров
Post #434
2.61K
Сегодня начинается спецкурс про изоморфизм графов, (чт, 17:05, 302 КПМ). Там Данила Дёмин будет рассказывать алгоритм Ласло Бабаи решения этой задачи за квазиполиномиальное время. Если планируете ходить, вступайте в чат https://t.me/+GiURflv_rt1lZGM6
Telegram Изоморфизм Графов за Квазиполиномиальное Время Данила Демин invites you to join this group on Telegram. Post #433
2.96K
compl-book.pdf9.1 MB
Текущая версия книги по сложности. Пока что в статусе черновика - многих разделов не хватает, где-то оставлены заметки to do. Надеюсь, будет получаться улучшать и дополнять текст в течение семестра. Если заметите ошибки или опечатки, пишите в личку.
Для тех, кто уже читал прежнюю версию: появилась первая глава с большим количеством интересного материала (история, обзор и т.д.), может быть интересно почитать.
Для тех, кто уже читал прежнюю версию: появилась первая глава с большим количеством интересного материала (история, обзор и т.д.), может быть интересно почитать.