Денис Тугарёв

Реализация булевых функций на непересекающихся множествах переменных

Продолжение доклада.

Александр Витвицкий

Реализация булевых функций на непересекающихся множествах переменных

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

Максим Гладких

Universal Relation Problem

Будут рассмотрены коммуникационные протоколы для этой задачи, базирующиеся на разных идеях, и имеющие сложность до n + 2 бит. Будет также доказана нижняя оценка для этой задачи в n + 1 бит.

Саша Головнёв

Алгоритмы разбиения на множества и их применения

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

Доклад по статье Björklund, Husfeldt, Koivisto, Set Partitioning via Inclusion–Exclusion.

Иван Близнец

Алгоритм проверки выполимости для булевых формул над полным бинарным базисом

В лекции будет приведен алгоритм для определения выполнимости булевых формул с длиной ограниченной $cn$, где $c$ -
некоторая константа, и заданными над базисом $B_2$. Доклад основан на статье:
"A Satisfiability Algorithm and Average-Case Hardness for Formula over the Full Binary Basis".

Денис Тугарёв

Реализация булевых функций на непересекающихся множествах переменных

Будут рассмотрены основные результаты статьи Wofgang J.Paul "Realizing boolean function on disjoint sets of variables" 1975. А именно доказательства следующих утверждений: для любого $\varepsilon > 0$ существует функция произвольной схемной сложности $f: \left\lbrace 0,1\right\rbrace^n \rightarrow \left\lbrace 0,1\right\rbrace^n$ такая, что $C(f \times f) \leqslant (1 + \varepsilon)C(f)$; для любого $\varepsilon > 0$ существует функция произвольной схемной сложности $g: \left\lbrace 0,1\right\rbrace^n \rightarrow \left\lbrace 0,1\right\rbrace$ такая, что $C(v\circ(g \times g)) \leqslant (1 + \varepsilon)C(g)$. Где $C(f), C(g)$ -- схемные сложности соответствующих булевых функций, $(f \times g)(x,y) = (f(x),g(y))$, $(f\circ g)(x) = f(g(x))$, $v:\left\lbrace 0,1 \right\rbrace^2 \rightarrow \left\lbrace 0,1 \right\rbrace$ и обозначает логическое OR.

Дмитрий Сердюк

Подсчёт количества совершенных паросочетаний

В данной лекции будет рассмотрен алгоритм для подсчета количества совершенных паросочетаний в графе на n вершинах, который использует полиномиальную память и $O^*(2^{n / 2})$ время. Ранее для этой задачи были был известен алгоритм, использующий экспоненциальную памать и $O(1.619^n)$ время (Коивисто) и алгоритм, использующий полиномиальную память и $O(1.942^n)$ время (Недерлоф). На лекции будет представлен алгоритм для подсчета хафниана матрицы над любым кольцом $R$ за $O^*(2^n)$ время.

Антон Тимофеев

Построение прямолинейных скелетов многоугольников в 3D

В докладе будут рассмотрены варианты построения прямолинейных скелетов многоугольников в трехмерном пространстве в общем и нескольких частных случаях.

Всеволод Опарин

Мощность SAT-солверов с запоминанием клозов и перезапусками

Мы изучим работу SAT-солвера с запоминанием клозов на невыполнимых формулах. Алгоритм будет рассмотрен как система доказательств. Ключевой вопрос: достаточно ли сильна такая система, чтобы иметь доказательства невыполнимости настолько же короткие как резолюционные?

Как окажется, любое резолюционное доказательство можно проэмулировать SAT-солвером, раздув его не более чем в полином.

Доклад по статье Knot Pipatsrisawat and Adnan Darwiche "On the Power of Clause-Learning SAT Solvers with Restarts".

Лёша Бешенов

Формулы Бриона

Продолжение доклада.