Семинары

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



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

Докладчик: 
А. Смаль
Дата: 
Monday, May 21, 2018 - 12:00
Место: 
402
Аннотация: 

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

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



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

Докладчик: 
Людмила Глинских
Дата: 
Friday, May 4, 2018 - 12:00
Место: 
402
Аннотация: 

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

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

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



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

Докладчик: 
А.С. Герасимов
Дата: 
Monday, January 15, 2018 - 14:00
Место: 
ауд. 106
Аннотация: 

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



Пятница 29.12. Александр Тискин: "Почти асинхронные вычисления: какие задачи можно эффективно решить за O(log p) раундов на p процессорах?"

Докладчик: 
Александр Тискин
Дата: 
Friday, December 29, 2017 - 12:00
Место: 
106
Аннотация: 

Вычислительная модель BSP (bulk-synchronous parallelism), предложенная и
теоретически проанализированная Leslie Valiant, в последние годы стала
широко использоваться в разработке параллельного программного
обеспечения (MapReduce, Pregel, Spark). Простота и элегантность BSP
достигается тем, что параллельное вычисление рассматривается в первом
приближении как последовательное - а конкретнее, состоящее из
последовательности асинхронных супершагов (раундов). На первый взляд
неочевидно, что многие нетривиальные задачи могут быть решены эффективно
за количество супершагов, не зависящее от размера входных данных, а
зависящее только от количества процессоров p. В докладе будет дан
краткий обзор алгоритмических задач, для которых известны "почти
асинхронные" эффективные BSP-алгоритмы, то есть алгоритмы, вычисляющие
решение всего за S = O(log p) супершагов без потери эффективности от
распараллеливания. В частности, широко известны алгоритмы с S = O(1) для
быстрого преобразования Фурье, сортировки, вычисления двумерной и
трехмерной выпуклой оболочки. Относительно недавно автором были
предложены алгоритмы с S = O(log log p) для вычисления суффиксного
массива строки и для выборки порядковой статистики последовательности, а
также неожиданные алгоритмы с S = O(log p) для определения всех попарных
кратчайших расстояний в графе и для вычисления наибольшей общей
подпоследовательности пары строк. Будет приведена попытка вычленить
общие подходы к разработке таких "почти асинхронных" алгоритмов, хотя в
настоящий момент это по-прежнему скорее искусство, чем точная наука.

Доклад будет продолжением выступления докладчика на конференции по
машинному обучению и анализу алгоритмов 18 декабря 2017 г., однако все
необходимые определения будут даны заново и знакомство с предыдущим
выступлением не требуется.



Пятница 22.12. Д.О. Соколов: "Monotone Circuit Lower Bounds from Resolution"

Докладчик: 
Д.О. Соколов
Дата: 
Friday, December 22, 2017 - 13:00
Место: 
402
Аннотация: 

Для любой формулы, которая сложна для резолюций, мы покажем что если заменить каждую переменную на функцию индексирования от новых переменных, то получится формула, которая является сложной для любой
семантической системы доказательств, строки которой могут быть вычислены эффективным коммуникационным протоколом (CP^*, CP, ...).

Данный результат представляет собой так называемую "lifting theorem" для графа запросов и коммуникационных протоколов на графах.

Доклад по совместной работе с Ankit Garg, Mika Göös и Pritish Kamath.

Внимание! Ориентировочная продолжительность доклада 2 пары: с 13-00 до 14-40 и с 16-00 до 17-40.


Pages