Seminars

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


Четверг 12.07. А. Кноп: "Стабильные сортировки слиянием"

Speaker: 
А. Кноп
Date: 
Thursday, July 12, 2018 - 18:00
Place: 
203
Abstract: 

Сортировка слиянием - это одна из самых популярных стабильных сортировок, она используется в большинстве стандартных библиотек на протяжении последних трех десятков лет. Однако сравнительно недавно Тим Питерс предложил модификацию этого алгоритма (Timsort) которая работает эффективнее на практике. Этот алгоритм стал стандартной сортировкой в Python и в Java. Однако с теоретической точки зрения его успех не был столь велик: первое доказательство того, что алгоритм сортирует n обьектов за O(n logn) операций было предложено лишь два года назад.

В докладе мы покажем что в худшем случае Timsort работает как минимум 1.5 n (log n + o(1)). Так же мы покажем оценки на ряд других алгоритмов устроенных подобно Timsort и предложим свой алгоритм (alpha-sort) которые работает эффективнее чем Timsort теоретичкски (гарантированное время работы alpha-sort меньше худшего времени работы Timsort) и в экспериментах.

Вторник 19.06. Navid Talebanfard (Institute of Mathematics of the Academy of Sciences of the Czech Republic): "Structure in Proof Complexity: The Case of Tseitin and Tree Decompositions"

Speaker: 
Navid Talebanfard (Institute of Mathematics of the Academy of Sciences of the Czech Republic)
Date: 
Tuesday, June 19, 2018 - 12:00
Place: 
402
Abstract: 

One of the main challenges in proving lower bounds in proof complexity is that we cannot (seemingly) make structural assumptions about the proof and thus our argument should work against any conceivable proof (which may not even exist). I will survey a few results showing that in some cases it is possible to prove structural properties of proofs of specific formulas or minimal proofs of arbitrary formulas. In particular I will give a more direct proof of our result with Galesi and Toran showing that the width of Tseitin formulas is the same in general and regular resolution.

Понедельник 21.05. А. Смаль: "Полудуплексная коммуникационная сложность"

Speaker: 
А. Смаль
Date: 
Monday, May 21, 2018 - 12:00
Place: 
402
Abstract: 

В классической модели коммуникационной сложности на каждом раунде коммуникации один из игроков говорит (посылает бит), а другой его слушает. Мы предлагаем рассмотреть обобщение этой модели, в которой Алиса и Боб могут также говорить одновременно (и тогда они не слышат друг друга) или слушать одновременно. Естественный аналог такой модели — это общение по полудуплексному каналу, например при помощи рации. Мы рассматриваем три варианта такой обобщённой модели и доказываем верхние и нижние оценки на коммуникационную сложность булевых функций в них.

По совместной работе с Иваном Михайлиным, Кеном Хувером и Расселом Импальяццо.

Пятница 04.05. Людмила Глинских : "Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs"

Speaker: 
Людмила Глинских
Date: 
Friday, May 4, 2018 - 12:00
Place: 
402
Abstract: 

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

Мы рассмотрим доказательство экспоненциальной нижней оценки для недетерминированных семантических 3-арных одноразовых ветвящихся программ — в таких программах каждой вершине диаграммы может соответствовать 3 различных значения.

Доклад по одноимённой работе Stephen Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi.

Понедельник 15.01. А.С. Герасимов: "Рациональная логика Павелки первого порядка: бесповторное гиперсеквенциальное исчисление и алгоритмы поиска вывода"

Speaker: 
А.С. Герасимов
Date: 
Monday, January 15, 2018 - 14:00
Place: 
ауд. 106
Abstract: 

Бесконечнозначная логика Лукасевича первого порядка \L$\forall$ и
её расширение рациональными истинностными константами --- рациональная логика Павелки первого порядка RPL$\forall$ --- являются одними из важнейших математических нечётких логик, формализующих приближённые рассуждения. В докладе мы представим ориентированное на поиск вывода снизу вверх гиперсеквенциальное исчисление GRP$\forall$ для RPL$\forall$, каждое правило которого обратимо и
не имеет ни в какой посылке повторений обозначений мультимножеств формул. Сравним (с точки зрения выводимости) GRP$\forall$ с другими исчислениями для \L$\forall$ и RPL$\forall$. Установим некоторые теоретико-доказательственные свойства GRP$\forall$, чем обеспечим основания для алгоритмов поиска вывода. Наконец, опишем семейство алгоритмов поиска вывода в табличном варианте исчисления GRP$\forall$.

Pages