Seminars

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



Понедельник 06.02. Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр): "Задачи распределения ресурсов и их алгоритмические свойства"

Speaker: 
Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр)
Date: 
Monday, February 6, 2017 - 14:00
Place: 
ауд. 106
Abstract: 

Задачи справедливого распределения (fair division) набора благ между агентами, имеющими различные предпочтения, представляют собой классическое направление на стыке математики и экономики. В последнее десятилетие оно переживает революцию в связи с приходом исследователей из Computer Science. Теперь многие механизмы распределения получают свое практическое воплощение в виде онлайн-сервисов таких как SPLIDDIT.ORG, а на первое место выходят вопросы об эффективности реализации. Учет этих вопросов может кардинально изменить понимание того, какие механизмы хороши, а какие нет. Так реализация некоторых механизмов ведет к NP-трудным задачам комбинаторной оптимизации, что делает их малопригодными на практике.

В этом обзорном докладе мы коснемся результатов последних лет и обсудим ряд открытых вопросов: для некоторых постановок неизвестна алгоритмическая сложность построения "хороших" дележей; для других --- даже их существование является лишь гипотезой.



Пятница 09.12. Galina Jiraskova (Mathematical Institute Slovak Academy of Sciences): " Self-Verifying Finite Automata"

Speaker: 
Galina Jiraskova (Mathematical Institute Slovak Academy of Sciences)
Date: 
Friday, December 9, 2016 - 16:00
Place: 
ауд. 311
Abstract: 

Consider a nondeterministic finite automaton $M$ over an alphabet $\Sigma$,
where the states can be either accepting, rejecting, or neutral. Let $L_a(M)$ (resp., $L_r(M)$) be the set of strings taking $M$ from the start state to an accepting state (resp., rejecting state). Then $M$ is said to be self-verifying
if $L_a(M) \cup L_r(M) = \Sigma^*$ and $L_a(M) \cap L_r(M) = \emptyset$.
That is, the strings reaching an accepting state and the strings reaching a rejecting state form a disjoint partition of $\Sigma^*$. The language accepted by $M$ is $L_a(M)$.

Using a result of Moon, Moser [On cliques in graphs, Israel J. Math. 3, 23--28, 1965], we get an optimal simulation of self-verifying automata by deterministic finite automata. Then we study the complexity of regular operations on languages represented by self-verifying automata, and get the tight upper bounds for union ($mn$), intersection ($mn$), reversal ($2n+1$), star (${3\over 4}2^n$), left quotient ($2^n-1$), right quotient ($3^{n/3}$), and asymptotically tight upper bound for concatenation ($3^{m/3}2^n$). Next we prove that given a nondeterministic automaton $M$ with accepting, rejecting, and neutral states, it is PSPACE-complete to determine if $M$ is self-verifying. Finally, we study the complexity of the membership, emptiness, universality, and minimization problems for self-verifying automata.



Понедельник 05.12. Н. Карпов: "Решение задачи 3-SUM с малой памятью и с малой глубиной дерева"

Speaker: 
Н. Карпов
Date: 
Monday, December 5, 2016 - 14:00
Place: 
106
Abstract: 

На семинаре мы рассмотрим алгоритм для задачи 3-SUM с малым количеством дополнительной памяти (примерно корень из n) и его обобщение на случай задачи k-SUM. Мы покажем почему это влечет ослабление 3-SUM гипотезы. Вдобавок, мы рассмотрим нетривиальное дерево решений глубины примерно n^1.5, где в каждом узле решение принимается на основе знака линейной комбинации константного набора входных чисел.



Миникурс по сложности пропозициональных доказательств. Лекция 2.

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

В первой части будет окончание предыдущей лекции, из теоремы Бен-Сассона и Вигдерсона будут выведены нижние оценки на цейтинские формулы и принцип Дирихле.
Во второй части А.А. Кноп расскажет про то, как нижние оценки для древовидных доказательств можно вывести из известных нижних оценок для коммуникационной сложности функции Disjointness. (Это результат Бима, Питасси и Сегерлинда в изложении Гуса и Питасси 2014 года)



О сложности вычисления симметрических функций

Speaker: 
Д.Ю. Григорьев (ПОМИ)
Date: 
Thursday, November 17, 2016 - 14:00
Place: 
ПОМИ, ауд. 203
Abstract: 

Вычисление симметрических функций - классическая тема, в частности, в сложности. Поскольку тема необозримая, то рассматриваются какие-то подклассы симметрических функций. Предполагается дать обзор более ранних результатов, а также рассказать о двух недавних сложностных оценках. Первая - экспоненциальная нижняя оценка сложности (совместно с Г.Кошевым) некоторой мономиальной симметрической функции при монотонных вычислениях (с использованием только сложений и умножений). Вторая - верхняя оценка монотонной сложности (совместно с С.Фоминым, Д.Ногненгом, Э.Шостом) полных симметрических функций, и как следствие - многочленов Шура. Обсудим также открытые вопросы.


Pages