Семинары

Рассылка: https://groups.google.com/forum/#!forum/spb-algo



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

Докладчик: 
Федор Сандомирский (НИУ ВШЭ, лаб. Теории Игр)
Дата: 
Monday, February 6, 2017 - 14:00
Место: 
ауд. 106
Аннотация: 

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

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



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

Докладчик: 
Galina Jiraskova (Mathematical Institute Slovak Academy of Sciences)
Дата: 
Friday, December 9, 2016 - 16:00
Место: 
ауд. 311
Аннотация: 

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 с малой памятью и с малой глубиной дерева"

Докладчик: 
Н. Карпов
Дата: 
Monday, December 5, 2016 - 14:00
Место: 
106
Аннотация: 

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



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

Докладчик: 
Д.М. Ицыксон, А.А. Кноп (ПОМИ РАН)
Дата: 
Friday, November 18, 2016 - 17:30
Место: 
ПОМИ, ауд. 203
Аннотация: 

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



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

Докладчик: 
Д.Ю. Григорьев (ПОМИ)
Дата: 
Thursday, November 17, 2016 - 14:00
Место: 
ПОМИ, ауд. 203
Аннотация: 

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


Pages