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

## 09.12.2014 Black-only и black-white pebble games (Михаил Слабодкин)

Доклад является выдержкой из статей Jakob Nordström и описывает базовые свойства black-only и black-white pebble games,
устанавливая связь некоторых параметров pebble игр с параметрами резолюционных доказательств: размером и variable space.

## 18.11.2014 Введение в гомотопическую теорию типов 2 (Кирилл Елагин)

Интерпретация теории типов в множествах. Тип равенства. Интерпретация теории типов в топологических пространствах, пространство путей. Основные свойства равенства.

## 28.10.2014 Введение в гомотопическую теорию типов 1 (Кирилл Елагин)

Теория множеств, логика и теория типов. Утверждения и суждения. Теория типов как основания математики. Классическая теория типов Мартин-Лёфа, связь с интуиционистской логикой и лямбда-исчислением.

## 23.09.2014 (Анна Малова) Нижняя оценка на размер дерева поиска противоречия для CSP, соответствующей лемме Шпернера.

Рассмотрим CSP, соответствующую лемме Шпернера в 2D. Используя игры Prover-a и Delayer-a,
докажем экспоненциальную нижнюю оценкку на размер дерева поиска противоречия.

## 25.11.2014 (Алексей Кладов) 2/3 приближённый алгоритм для MAX-ATSP.

В задаче MAX-ATSP требуется найти гамильтонов цикл максимального веса
в полном взвешенном ориентированном графе. Мы получим $\frac{2}{3}$
приближение при помощи округления решения линейной программы. Из
получающегося таким образом d-регулярного мультиграфа можно будет
извлечь пару покрытий циклами большого веса, в которых можно найти
гамильтонов тур, вес которого не меньше чем $\frac{2}{3}$ от
оптимального.

## 21.10.2014 (Николай Карпов) Параметризованные алгоритмы для Secluded Path и Secluded Steiner Tree.

Мы рассмотрим задачу Seclude Path и Secluded Steiner Tree и параметризованные алгоритмы для их решения.
• Алгоритм, параметризованный максимальной степенью вершины, для Secluded Path.
• Алгоритмы, параметризованные размером ответа, $3^{\frac{k}{3}}$ для пути и $2^{k}$ для дерева.
• Алгоритм, параметризованный Tree Width, с временем работы $4^{tw}$.
• ## 07.10.2014 (Павел Чуприков) Верхние и нижние оценки на онлайн алгоритмы для shared-memory буфера с пакетами одинаковой стоимости.

Рассмотрим shared-memory модель организации буфера. Вспомним соревновательный подход к анализу алгоритмов. Дадим общую для всех онлайн алгоритмов нижнюю оценку $\frac{4}{3}$ в данной модели. Рассмотрим алгоритм LQD (Largest Queue Drop) для случая, когда пакеты имеют равную стоимость. Дадим для LQD константную верхнюю оценку $2$.

## 09.09.2014 (Михаил Слабодкин) Resolution complexity of perfect matching principles for sparse graphs.

We construct a constant degree bipartite graph $G_n$ such that the resolution
complexity of the perfect matching principle for $G_n$ is $2^{\Omega(n)}$,
where $n$ is the number of vertices in $G_n$. We also prove the following corollary.
For every natural number $d$,for every $n$ large enough, for every function
$h:\{1,2,\dots, n\}\to \{1,2,\dots, d\}$, we construct a graph with $n$ vertices
that has the following properties:
• There exists a constant $D$ such that the