А. Тимофеев

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

В докладе будут представлены несколько результатов в области преобразования наборов замкнутых контуров (многоугольников) и планарных укладок графов.

Задача поиска преобразования (морфинга) будет разобрана в нескольких различных постановках, от очень узких классов (ортогонально-выпуклых многоугольников и монотонного морфинга на них), где она оказывается NP-трудной, до очень общего случая допускающего набор непростых многоугольников с "дырками".

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

Ф. Парт (Академический университет)

Parameterized complexity

Доклад посвящен основам parameterized complexity. Первая часть доклада будет
посвящена иерархии замкнутых относительно сведения классов параметризованных
задач W[k]. Во второй части будет рассказано как из предположений о
неравенстве некоторых классов W[k] можно получать неприближаемости
аппроксимационными схемами тех или иных задач, а также о нижних оценках на
ядра.

В. Николаенко (Академический университет)

Нижние оценки на схемную сложность

Доклад будет посвящен нижним оценкам на схемную сложность. Будет
рассказан результат 2010 года (J. Kinne, D. van Melkebeek, R.
Shaltiel), который является улучшением и упрощением результата 2004
года (V. Kabanets, R. Impagliazzo). В первой части доклада будет
показана нижняя оценка на схемы в предположении существования
алгоритма для распознавания ACZ (язык арифметических схем, вычисляющих
нулевые многочлены) с ограниченной ошибкой. Во второй части доклада
будет показана параметризация результата Kabanets и Impagliazzo.

А. Давыдов (Академический университет)

Сжатие строк

В докладе будет рассказано о сжатии строк с помощью NSLP, также о сложности некоторых классических групповых задач. Будут поставлены вопросы о сложности аналогичных задач на
сжатых строках.

А. Головнев (Академический университет)

Эффективное решение MAX-2-SAT

В докладе будут рассмотрены лучшие известные алгоритмы для задач MAX
2-SAT, MAX 2-CSP, MAX CUT.
Будут предложены новые алгоритмы решения этих задач. В частности,
будет рассмотрен алгоритм решения задачи MAX 2-SAT с оценкой сложности
$O^*(2^{n(1-3.677/(d+1))})$.

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

Эффективный Nullstellensatz (продолжение)

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

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

Эффективный Nullstellensatz

В докладе будет рассказано о верхних и нижних оценках на многочлены в
равенстве Безу; изложены идеи алгоритма их поиска.

И. Близнец (Академический университет)

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

В докладе будут рассказаны некоторые алгоритмы касающиеся задачи MAX-SAT. А именно:
1) Алгоритм Вильямса для MAX-2-SAT.
2) Простой алгоритм для (n,3)-MAX-SAT, с оценкой времени работы в зависимости от количества клозов.
3) Обзор самого быстрого алгоритма для MAX-SAT, предложенного Ченом и Канжем (Jianer Chen, Iyad A. Kanj).

С. Исакова (Академический Университет)

Типизированное лямбда-исчисление

В докладе будет рассказано, что такое изоморфизм Карри-Говарда. Это прямое
соответствие между формулами и доказательствами в интуиционистской логике и
программами (термами) и их типами в типизированном лямбда-исчислении. Будут
введены все необходимые для этого определения и понятия. В завершении будет
показано, как задача QBF сводится к задаче построения терма с заданным
типом.

А. Бешенов (Академический Университет)

Вычисления в алгебрах (продолжение)

Продолжение доклада (на прошлом семинаре были определены основные понятия).