Ф. Парт (АУ)

Сложность параметризованных резолюций

Доклад по статье: Beyersdorff, Galesi, Laura "Hardness of Parameterized
Resolution"

Доклад будет посвящен последним результатам в области сложности
параметризованных доказательств. Это направление Computer Science возникло
совсем недавно с целью посредством доказательства нижних оценок для
параметризованных систем доказательств получить неравенство классов
параметризованных языков W[2] и co-W[2], а значит и неравенство W[2] и FPT.
В первой статье Dantchev et al. "Parameterized proof complexity" были
сформулированы основные определения, а также приведена классификация размера
параметризованных tree-like резолюций на семействах пропозициональных
формул, являющихся записью формул логики первого порядка для конечных
моделей. В частности, было доказано, что параметризованные tree-like
резолюции не fpt-ограничены т.е. имеют большие доказательства на некоторых
семействах формул. В статье "Hardness of Parameterized Resolution" этот
результат был передоказан с использованием асимметричного варианта игр
Prover'a и Deleyer'a, что позволяет обойтись без привлечения формул первого
порядка. Также в статье приводятся следующие результаты:

1) Определяется класс семейств параметризованных противоречий, имеющих
короткие доказательства в параметризованных tree-like резолюциях.
2) Доказывается, что параметризованные dag-like резолюции не fpt-ограничены.
Для этого применяются игры Prover'a и Delayer'a придуманные Пудлаком для
доказательства нижних оценок на обычные dag-like резолюции.

А. Бешенов (АУ)

Полуалгебраические множества и цилиндрическое алгебраическое разбиение. Часть II

На прошлом семинаре мы вспомнили теорему Тарского--Зайденберга, а
также узнали в общих чертах, что изучает полуалгебраическая и
о-минимальная геометрия. Во второй части я определю цилиндрическое
алгебраическое разбиение, объясню алгоритм и его пользу для
человечества.

А. Давыдов (АУ)

Новые конструкции надёжных в слабом смысле криптографических примитивов

Доклад по собственным результатам.

Приводится новый метод доказательства и новые конструкции линейных криптографических примитивов, надёжных в слабом смысле.

Ю. Беляева (Академический Университет).

Явная конструкция графов Рамсея без треугольников.

Число Рамсея $ R(3,m) $ это минимальное число $ n $ такое что любой граф из $ n $ вершин содержит либо треугольник, либо независимое множество размера $ m $. Для чисел Рамсея $ R(3, m) $ при помощи вероятностного метода была доказана оценка $ \Theta(m^2/\log{m}) $. Представляет большой интерес задача построения примеров графов без треугольников, с числом независимости $ m $ и с как можно большим числом вершин. В докладе будет описана явная конструкция графа не содержащего треугольников и независимых множеств размера $ m $ с $ \Omega(m^{3/2}) $ вершинами приведённая в статье Noga Alon ``Explicit Ramsey graphs and orthonormal labelings''. Семейство таких графов это графы Кэли, полученные с использованием проверочных матриц БЧХ-кодов. Для доказательства оценки на размер независимого множества в полученном графе будет использована $ \theta $-функция Ловаса.