Ю. Беляева (АУ)
Семейства множеств с ограниченным размером пересечений и явная
конструкция графов Рамсея

В докладе будет рассказано о семействах множеств с ограниченным числом
пересечений. Семейство множеств называется L-пересекающимся, если
размер пересечения любых двух элементов из семейства принадлежит
множеству L. В докладе будут приведены оценки на размер
L-пересекающихся семейств для случаев равномерного и неравномерного
семейства. Также будет рассказано обобщение известного модульного
варианта этих оценок, доказанного в P.Frankl, R.M.Wilson "Intersection
theorems with geometric consequences", в котором рассматриваются не
сами размеры пересечений, а их остатки по некоторому простому модулю
p. Будут изложены доказательства, представленные в N.Alon, L.Babai,
H.Suzuki "Multilinear polynomials and Frankl - Ray-Chaudhuri - Wilson
type intersection theorems", использующие линейные пространства
полиномов. В качестве следствия рассказанных результатов будет
приведена явная конструкция графов Рамсея суперполиномиальным числом
вершин.

Ф. Парт (АУ)
Моделирование одной машины Тьюринга на другой

Доклад по материалам лекции А. Ромащенко. На докладе будет разобрана
проблема построения эффективной универсальной машины Тьюринга.
В частности, будет рассмотрен алгоритм моделирования многоленточной машины
Тьюринга на двухленточной с замедлением в логарифм.

В. Николаенко (АФТУ)
Алгоритм Берлекэмпа

В этом докладе будет рассказано об алгоритме Берлекэмпа разложения полнимов на множители в полях простой мощности, и в качестве подзадаче о тесте на неприводимость. Будет также расказано, как улучшить оценку на время работы, сделав алгоритм вероятностным.

С. Капулкин (АФТУ)
p-оптимальные системы доказательств

$По\; статье\; \text{'}\text{'}Optimal\; acceptors\; and\; optimal\; proof\; systems\text{'}\text{'},\; автор\; Э.А.Гирш.$
Доклад является введением в проблематику систем доказательств и аксепторов. Поиск системы доказательств для языка тавтологий с доказательствами полиномиальной длины связан с вопросом $\mathbf{NP}$ vs $\mathbf{co{-}NP}$. Акспеторами называются машины, останавливающиеся на входах из языка и только на них. В докладе показывается связь между существованием p-оптимальных систем доказательств и оптимальных аксепторов. Доказывается существование p-оптимальных систем доказательств с одним битом подсказки.

Д. Соколов (АФТУ)
Криптографическая стойкость функции Голдрейха

Функция Голдрейха - кандидат в односторонние функции. В докладе будут рассмотрены нижние оценки на время обращения функции Голдрейха при помощи подкласса DPLL алгоритмов - "пьяных" алгоритмов. Будет доказана нижняя экспоненциальная оценка на время работы любого DPLL алгоритма на невыполнимой булевой формуле, полученной по функции Голдрейха, а также показано, что после некоторого числа шагов "пьяного" алгоритма с большой вероятностью формула станет невыполнимой.
Также в докладе будет приведена явная конструкция функции Голдрейха, обеспечивающая указанные оценки.

С. Исакова (АФТУ)
Схемная сложность обратных функций

Доклад по статье Jean-Camille Birget "On the circuit-size of inverses".
Фундаментальным в криптографии является вопрос о сложности обращения
функции. В рассматриваемой статье ключевым является несколько похожий
вопрос: "какого размера может быть обратная функция". Устанавливается связь
между такими, на первый взгляд, не очень связанными понятиями, как схемная
сложность обратных функций и классы сложности. А именно, в докладе будет
рассмотрена и доказана следующая теорема:
Если существует ограничение на размер обратной функции (точнее, если
существует полином, который для любой ациклической булевой схемы C
ограничивает размер обратной схемы C'), то полиномиальная иерархия
схлопывается до второго уровня.

Ф. Парт (АФТУ)
Параметризованные системы доказательств

Вопрос о равенстве классов co-NP и NP имеет естественную переформулировку в терминах систем доказательств и сложности доказательств. Аналогично, те или иные классы задач с параметром W[t] могут быть отделены от соответствующих им co-классов посредством исследования параметризованных систем доказательств и оценке снизу размера доказательств в таких системах. В докладе будет рассмотрена параметризованная версия tree-like резолюций для задачи ограниченной невыполнимости и приведена классификация (модифицированная теорема Риса) длины доказательств в этой системе для семейств параметризованных противоречий, являющихся записями для конечных моделей формулы логики первого порядка, не имеющей конечных моделей.

Ю. Беляева (АФТУ)
Гипотеза о песочных часах

Доклад посвящён гипотезе о песочных часах (sandglass conjecture), предложенной в статье Rudolf Ahlswede, Gabor Simonyi "Note on the optimal structure of recovering set pairs in lattices: the sandglass conjecture". Гипотеза говорит о семействах подмножеств конечной решётки, удовлетворяющих двум ограничениям -- "восстанавливающих парах" (recovering pair) подмножеств и предлагает оценку на произведение их мощностей. Данная оценка в общем случае не доказана. В докладе будет рассмотрен частный случай гипотезы для решётки подмножеств конечного множества и доказана наилучшая известная оценка для этого случая представленная в работе Ron Holzman, Janos Korner "Cancellative pairs of families of sets". Также будет изложена идея доказательства гипотезы для решётки представляемой в виде произведения двух цепей.

В. Николаенко (АФТУ)
Перестановочные полиномы

В этом докладе будет рассказано об исследованиях перестановочных биномов над конечными полями. Будет освещен вопрос актуальности исследований в сфере криптографических протоколов. Также будет рассказано о диаграммах Юнга и других характеристиках перестановок. Будут приведены теоретические результаты для колец $\$Z/(2^nZ)\$$, рассказано о критериях перестановочности и полученных автором доклада численных и статистических результатах для оценки числа полиномов в зависимости от размера поля.

С. Капулкин (АФТУ)
Иерархия по времени вычислений с подсказкой

Доклад по статье Melkebeek, Pervyshev "A Generic Time Hierarchy for Semantic Models With One Bit of Advice". В докладе будет рассмотрена иерархия по времени для семантических классов с подсказкой. Будет дано достаточно общее определение семантического класса, включающее в себя такие классы, как RP, BPP, AM и другие. Будет сформулирована и доказана следующая теорема:
Для любой разумной семантической модели вычислений и любых констант a и c найдется язык, вычислимый за полиномиальное время с одним битом подсказки, но не за время $\$n^c\$\; с\; \$a\$$ битами подсказки.