Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



Приближённые алгоритмы для Feedback vertex set

Speaker: 
Всеволод Опарин
Date: 
Monday, July 21, 2014 - 18:00
Place: 
ПОМИ, ауд. 203
Abstract: 

Я расскажу про два подхода при приближенном решении задачи Feedback vertex set. Первый подход является комбинаторным, основывается на технике расслоения и дает 2-приближение. Второй метод называется прямодвойственным (primal-dual), дает 4 log_2 n - приближение. Мы формулируем задачу в терминах LP, находим ей дуальную и на основе дуальной строим эффективный алгоритм.



О сложности задачи выполнимости схемы

Speaker: 
Иван Михайлин
Date: 
Thursday, June 19, 2014 - 13:00
Place: 
ПОМИ, ауд. 203
Abstract: 

В докладе будет доказано, что из разумных предположений на схемную сложность NP-полных задач следует, что любой полиномиальный алгоритм с односторонней ошибкой для Circuit-SAT будет давать очень маленькую вероятность успеха.



Задача поиска кратчайшего цикла в графе через выбранные вершины

Speaker: 
Роман Демидов
Date: 
Wednesday, April 23, 2014 - 18:00
Place: 
ПОМИ, Мраморный зал
Abstract: 

В своем докладе я расскажу вероятностный с односторонней ошибкой 2^k poly(n) алгоритм Бьорклунда-Хасфельдта-Тасламан для задачи нахождения k-цикла в неориентированном графе (т.е цикла, проходящего через k заданных вершин/рёбер), а также расскажу про другой результат Вальстрема для той же задачи.



Расщепление по линейным равенствам

Speaker: 
Дмитрий Ицыксон
Date: 
Friday, April 11, 2014 - 17:00
Place: 
ПОМИ, ауд. 203
Abstract: 

Мы рассматриваем алгоритмы для SAT, которые могут расщепляться по значениям линейных равенств по модулю 2. Например, в одной ветви он может рассматривать случай, что x+y+z=0, а в другой, что x+y+z=1. Будет рассказана экспоненциальная нижняя оценка на время работы всех таких алгоритмов для формул, кодирующих принцип Дирихле. Доказательство этого результата элементарно. Также мы поговорим о связанных с этим алгоритмом системах доказательств (аналог метода резолюций, но работающий с линейными равенствами вместо литералов), для таких систем доказательств мы докажем полиномиальную эквивалентность семантической и синтаксической версии и импликационную полноту.

Летом 2013 года Дима рассказывал нижнюю оценку через коммуникационную сложность. Если останется время, то я расскажу предложенное А. Шенем упрощенное изложение Диминого результата. Доклад не будет зависить от предыдущего Диминого доклада и никаких предварительных знаний не требуется. В конце будет сформулировано несколько открытых вопросов, среди них есть те, которые реально закрыть.


Pages