Теоретический семинар (осень 2010)

10-00 А. Головнев (Академический Университет)
Новая верхняя оценка для задачи (n,3)-MAX-2-SAT

Доклад по результатам докладчика.

12-00 А. Подхалюзин (Академический Университет)

Алгоритм решения задачи MAX-2-XSAT

Доклад по результатам докладчика.

14-00 В. Опарин (Академический Университет)

Cache-oblivious algorithms

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

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

И. Близнец (АУ)

Алгоритмы для $(n,3)$-MAX-SAT

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

Приводятся полученные методом разбора случаев улучшенные оценки для $(n,3)$-MAX-SAT, одного из NP-полных вариантов задачи максимальной выполнимости, в котором каждая переменная появляется в формуле не более чем три раза.

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

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

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

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

С. Исакова (АУ)

Сложность задачи вывода типов в лямбда-исчислении

Доклад по статье:
Harry G.Mairson "Linear lambda calculus and PTIME-completeness".

В докладе определяются формализмы лямбда-исчисления, просто типизированного
лямбда-исчисления (a la Curry) и рассматривается задача вывода типов в
последнем. Доказывается P-полнота данной задачи при помощи сведения к ней P-полной
задачи о значении булевой схемы на заданном входе. При этом приводится простая
конструкция с использованием стандартных комбинаторов Черча.

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

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

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

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

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

Полуалгебраические множества представляют собой вещественные решения
систем полиномиальных уравнений и неравенств. Очень важный факт
устанавливает теорема Тарского--Зайденберга: всякая проекция
полуалгебраического множества также является полуалгебраическим
множеством. Это означает, что для вещественных чисел и сигнатуры (=,
<, 0, 1, +, *) возможна элиминация кванторов.

Ф. Парт (АУ)

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

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

В. Николаенко

Существование полных множеств

В докладе будет рассмотрено определение класса языков Sparse. Будет доказан факт, о том, что
существование оптимальной системы доказательств для тавтологий влечет существование полного языка в классе
$NP \cap Sparce$. Также в докладе будут рассмотрены promise классы и будет доказан следующий факт:
если существует оптимальная система доказательств для TAUT, то существует полное множемтво для promise
классов ($NP \cap co-NP, ZPP, BPP, RP, ...$)

С.Капулкин (АУ)

DIR - Distributed Information Retrieval

В общем виде проблема распределенного поиска ставится следующим образом.
Есть несколько (возможно различных) поисковых систем, каждая из которых
ведет поиск в своей коллекции документов. Коллекции могут пересекаться.
Задача поиска - перенаправить поисковый запрос этим системам и корректно
обработать полученные результаты.

Страницы