Project Seminar 2019 2020
Содержание
- 1 Расписание
- 2 Проведённые семинары
- 2.1 Семинар 1 (12 сентября).
- 2.2 Семинар 2 (19 сентября).
- 2.3 Семинар 3 (26 сентября).
- 2.4 Семинар 4 (3 октября).
- 2.5 Семинар 5 (10 октября).
- 2.6 Семинар 6 (17 октября).
- 2.7 Семинар 7 (31 октября).
- 2.8 Семинар 8 (7 ноября).
- 2.9 Семинар 9 (14 ноября).
- 2.10 Семинар 10 (5 декабря).
- 2.11 Семинар 11 (12 декабря).
- 2.12 Семинар 12 (21 января).
- 2.13 Семинар 13 (28 января).
- 2.14 Семинар 14 (11 февраля).
- 2.15 Семинар 14 (19 февраля).
- 3 Предлагаемые статьи для рассказа на семинаре
- 4 Преподаватели
Расписание
Семинар проходить по четвергам с 18.10 по 19.30
Проведённые семинары
Семинар 1 (12 сентября).
Задача равенства нулю многочлена. Лемма Шварца-Зиппеля.
Семинар 2 (19 сентября).
Применение задачи равенства нулю многочлена для решения задачи о паросочетаниях. Дерандомизация задачи о равенстве нулю многочлена для случая небольшого числа ненулевых мономов.
Семинар 3 (26 сентября).
Дерандомизация задачи о равенстве нулю многочлена с помощью теорем типа Сильвестра-Галлаи.
Семинар 4 (3 октября).
Доклад Антона Гнатенко
Семинар 5 (10 октября).
Доклад Антона Гнатенко.
Анонс:
Конечные автоматы, задающие преобразования потоков входных сигналов в последовательности элементарных действий, являются простейшей моделью вычислений, пригодной для описания поведения реагирующих систем. Это поведение проявляется в соответствии между потоком входных сигналов и последовательностью элементарных действий, выполняемых системой. Для формальной спецификации и верификации реагирующих систем такого рода требуются более сложные и выразительные средства спецификации, нежели традиционные темпоральные логики. В докладе будет предложена расширенная темпоральная логика Reg-CTL*, в которой темпоральные операторы параметризованы регулярными выражениями. Мы рассмотрим алгоритмы верификации автоматов-преобразователей относительно формул некоторых фраментов этой логики, а также её выразительные возможности. На правах "work in progress" будет изложена идея алгоритма верифкации относительно произвольных формул Reg-CTL*.
Семинар 6 (17 октября).
Доклад Антона Гнатенко.
Семинар 7 (31 октября).
Эффективное решение задачи SAT для КНФ маленькой ширины.
Семинар 8 (7 ноября).
Доклад Андрея Фёдорова.
Семинар 9 (14 ноября).
Доклад Виктора.
Семинар 10 (5 декабря).
О задаче QBF для КНФ маленькой ширины
Семинар 11 (12 декабря).
Доклад Анастасии Чистопольской.
Семинар 12 (21 января).
Введение в Grain-Fine complexity
Семинар 13 (28 января).
Введение в Grain-Fine complexity (продолжение)
Семинар 14 (11 февраля).
Доклад Азата
Семинар 14 (19 февраля).
Доклад Павла Захарова
Предлагаемые статьи для рассказа на семинаре
1) Nitin Saxena, Progress on Polynomial Identity Testing https://eccc.weizmann.ac.il/report/2009/101/
2) Лекции Стэндфордского университета о PIT и совершенных паросочетаниях. https://cs.stanford.edu/~mpkim/notes/lec5.pdf
Преподаватели
Милованов Алексей, almas239@gmail.com
