Seminars

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



Миникурс по сложности пропозициональных доказательств. Ширина и размер резолюционных доказательств

Speaker: 
Ицыксон Д.М. (ПОМИ РАН)
Date: 
Friday, November 11, 2016 - 17:30
Place: 
ПОМИ, ауд. 203
Abstract: 

Миникурс предназначен для студентов, аспирантов и всех интересующихся сложностью пропозициональных доказательств.
В первой лекции будет рассказано о резолюционной системе доказательств. В частности, мы изучим теорему Бен-Сассона и Вигдерсона о связи ширины и размера резолюционных доказательств. В качестве следствия будет приведены доказательства экспоненциальных нижних оценок на размер доказательства цейтинских формул и принципа Дирихле.



Автоматический логический вывод в интуиционистских логических исчислениях обратным методом Маслова

Speaker: 
Павлов В.А. (СПбПУ)
Date: 
Monday, November 7, 2016 - 14:00
Place: 
ПОМИ, ауд. 106
Abstract: 

Рассматривается применение обратного метода Маслова для автоматического логического вывода в интуиционистской логике первого порядка. На данный момент существует немного программных реализаций обратного метода для этой логики, при этом остаётся пробел между теоретическими достижениями и их внедрением на практике.
Разработано новое исчисление обратного метода для интуиционистской логики первого порядка и стратегии логического вывода для этого исчисления.
Разработан алгоритм логического вывода с возможностью комбинирования стратегий, применимый к предложенному исчислению и к другим исчислениям обратного метода. На основе алгоритма разработана программа автоматического логического вывода WhaleProver.
Проведено экспериментальное сравнение используемых стратегий по ряду критериев, выявлена оптимальная комбинация стратегий.
Программа WhaleProver апробирована на обширной библиотеке задач ILTP версии 1.1.2. Всего программа решила 810 задач, что сопоставимо с результатами лучших аналогов. Решён ряд новых задач. Программу можно использовать для обучения или интегрировать в существующие системы искусственного интеллекта.



О теоретико-групповом обобщении теоремы Морса и Хедлунда

Speaker: 
Светлана Пузынина (Институт Математики им. Л. С. Соболева)
Date: 
Monday, October 31, 2016 - 14:00
Place: 
ПОМИ, ауд. 106
Abstract: 

В классической работе 1938 года Морс и Хедлунд доказали, что всякое непериодическое бесконечное слово содержит как минимум n+1 подслово длины n. Более того, бесконечное слово содержит ровно n+1 подслово для каждой длины n, если и только если оно бинарное, непериодическое и сбалансированное, т.е. является словом Штурма. В докладе мы рассмотрим обобщение понятия сложности слов через действия групп и обсудим обобщения теоремы Морса и Хедлунда.



Approximation and Parameterized Complexity of Minimax Approval Voting

Speaker: 
Krzysztof Sornat (University of Wroclaw)
Date: 
Monday, October 17, 2016 - 14:00
Place: 
ПОМИ, ауд. 106
Abstract: 

We present three results on the complexity of Minimax Approval Voting that is a voting rule for choosing committee of fixed size k. Here, we see the votes and the choice as 0-1 strings of length m (characteristic vertors of the subsets). The goal is to minimize the maximum Hamming distance to a vote. First, we study Minimax Approval Voting parameterized by the Hamming distance d from the solution to the votes. We show Minimax Approval Voting admits no algorithm running in time O*(2^o(d\log d)), unless the Exponential Time Hypothesis (ETH) fails. This means that the O*(d^(2d)) algorithm of Misra et al. [AAMAS 2015] is essentially optimal. Motivated by this, we then show a parameterized approximation scheme, running in time O*((3/eps)^(2d)), which is essentially tight assuming ETH. Finally, we get a new polynomial-time randomized approximation scheme for Minimax Approval Voting, which runs in time n^O(log(1/eps)/eps^2) * poly(m), almost matching the running time of the fastest known PTAS for Closest String due to Ma and Sun [SIAM J. Comp. 2009].
Authors: Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat


Pages