Семинары

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



Пятница 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
Аннотация: 

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



Амплификация сложности для некоммутативных арифметических схем

Докладчик: 
Иван Михайлин
Дата: 
Thursday, November 17, 2016 - 11:00
Место: 
ПОМИ, ауд. 402
Аннотация: 

Размер арифметических схем является одним из наиболее естественных мер сложности полиномов. Так как арифметические схемы обобщают булевы схемы, доказывать для них нижние оценки должно быть проще, поэтому доказательство суперполиномиальной нижней оценки на размер арифметических схем для явно заданного полинома будет очень неплохим
разогревом перед доказательством "NC_1 не содержит P". К сожалению, несмотря на многолетние изучение, прогресс в этом направление не внушает оптимизма.
Чтобы еще немного упростить вопрос, можно рассмотреть модель некоммутативных арифметических схем. Это звучит как очень хорошая идея, так как некоммутативные арифметические схемы является прямым обобщением обычных арифметических схем. К тому же для некоммутативных арифметических формул мы знаем экспоненциальные нижние оценки. Однако
для схем не удалось получить никаких новых результатов. В докладе будет предложено объяснение, почему доказать суперлинейную нижнюю оценку может оказаться сложнее чем казалось изначально. А именно: такая оценка может быть амплифицированна до суперполиномиальной.


Pages