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

Теорема о параметричности (Parametricity Theorem) Филипа Вадлера
позволяет доказывать утверждения (так называемые «свободные теоремы»)
про параметрически-полиморфные функции, пользуясь только типами этих функций.
В результате получаются теоремы вида «любая функция, имеющая данный тип,
обладает таким-то свойством».

Мы познакомимся с полимофрным λ-исчислением (также известным как System F),
докажем для него Теорему о параметричности и посмотрим, что с её помощью

План доклада:
  1. Что такое раскраска, списочная раскраска, векторная раскраска.
  2. Определение задачи полуопределенного программирования.
  3. Если есть $f(n)$ приближение для максимальной подклики, то есть алгоритм, красящий 3-раскрашиваемый граф в $f(n)\cdot \log n$ цветов.
  4. Алгоритм Wigderson-а раскраски 3-раскрашиваемого графа в $\sqrt{n}$ цветов.
  5. Алгоритм 3-раскрашиваемого графа в $n^{0.38}$ цветов.

В рамках общей задачи сегментации изображений рассмотрим быстрый приближенный алгоритм для NP-трудной задачи Normalized-Cut с линейными априорными ограничениями, а также задачу Biased Normalised-Cut с ограничениями другого вида.

Рассмотрим определения TCAM, правил классификации пакетов. Обсудим проблемы интервальных правил и простейшие методы их решения. Определим database-dependent и database-independent методы. Предложим новый database-dependent метод и определим вспомогательную задачу MLIC. Полиномиальный 2-приближающий MLIC алгоритм. Рассмотрим database-independent метод SGRE.

Обсудим субэкспоненциальные алгоритмы: введём $SERF$-сведение и докажем полноту относительно него для некоторых задач. Также рассмотрим вопрос о доказательстве нижних оценок. Рассмотрим нижние оценки для $AC^0$. Покажем, что с большой долей вероятности случайные полиномы второй степени для $GF(2)$ требуют экспоненциальный размер для схем $\Sigma_3^k$ при $k=o(\log \log n)$. Как следствие, получим пcевдослучайный генератор.

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