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

Доклад по статьям:
D. Gutfreund, R. Shaltiel, A. Ta-Shma. If NP languages are hard on the worst-case then it is easy to find their hard instances.
N. Vereschagin. Improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case then it is Easy to Find Their Hard Instances".
Известно, что случайная булева функция от $n$ переменных требует схем размера $\Theta(2^n/n)$. В то же время наилучшей нижней оценкой для явно заданной булевой функции (то есть функции из $NP$) является оценка $3n−o(n)$, доказанная Блюмом более тридцати лет назад. Эта оценка, как и почти все предыдущие, доказана методом элиминации гейтов.
Для выполнимых цейтинских формул для полного графа на n вершинах оценка на размер OBDD с любым порядком переменных — $2^{\Omega(\sqrt{n})}$. В данном докладе будет определено понятие цейтинской формулы и доказана данная оценка.

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

Будет рассказана связь алгоритмов для решения задачи $\#CircuitSAT$ (вычислить количество выполняющих наборов для булевой схемы) и нижних оценок на размер булевых схем.

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

Мы определим понятие онлайн задачи и онлайн алгоритма. Рассмотрим методы оценки эффективности таких алгоритмов, и связанные с ними виды научных результатов (на примере задачи "О выделении страниц памяти"). Затем перейдем к задаче управления буфером и докажем некоторые нижние оценки для онлайн алгоритмов решения данной задачи.

Начало семинара будет посвящено сложности булевых функций и различных её мерах, мы сформулируем Sensitivity Conjecture и обсудим её связь с некой коммуникационной игрой.
В ней Алиса и Боб пытаются не быть обманутыми Евой или заплатить за обман маленькую цену. Оценки на цену препятствия обману будут тесно (с некоторой стороны) связаны с чувствительностью широкого класса функций. Мы обсудим нетривиальные стратегии в игре и её вариациях, нижние оценки на протоколы особого вида и рассмотрим некоторые эквивалентные переформулировки игры, поддающиеся (с натяжкой) анализу на компьютерах.

Мы рассмотрим задачу реберного дополнения до класса графов $\mathcal{G}$. В такой задаче нам на вход задан граф H и целое k, требуется к графу H добавить не более k ребер так, чтобы полученный граф принадлежал классу $\mathcal{G}$. В докладе будут рассмотрены такие классы графов, которые можно охарактеризовать с помощью множества (конечного или бесконечного) запрещенных индуцированных подграфов $\mathcal{F}$. Мы рассмотрим вопросы связанные с нижними оценками на вычислимость, а также приближаемость таких задач.

Будут доказаны нижние оценки на размер упорядоченных бинарных диаграмм решений для некоторых функций.

Страницы