Seminars

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


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

Speaker: 
Александр Тискин
Date: 
Friday, December 29, 2017 - 12:00
Place: 
106
Abstract: 

Вычислительная модель 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"

Speaker: 
Д.О. Соколов
Date: 
Friday, December 22, 2017 - 13:00
Place: 
402
Abstract: 

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

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

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

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

Пятница 15.12. А. Смаль: "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster"

Speaker: 
А. Смаль
Date: 
Friday, December 15, 2017 - 12:00
Place: 
402
Abstract: 

Доклад по статье Dominik Scheder, John Steinberger "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster" (http://drops.dagstuhl.de/opus/volltexte/2017/7535/)

В докладе будет представлено простое изложение статьи Хертли о PPSZ. Кроме того будет показано, что если мы улучшим PPSZ для Unique-k-SAT, то из этого получится улучшение для обычного k-SAT (но с худшими параметрами).

Понедельник 11.12. Смаль А.: "PPZ lowerbound via entropy"

Speaker: 
Смаль А.
Date: 
Monday, December 11, 2017 - 12:00
Place: 
402
Abstract: 

На семинаре мы рассмотрим простое доказательство основной теоремы из статьи Or Meir, Avi Wigderson "Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds" (https://eccc.weizmann.ac.il/report/2017/149/), а точнее её более сильной версии. Кроме того, будет показано, как из этой более сильной теоремы следует нижняя оценка 2^(n/k - 1) на размер схемы глубины 3 (OR-k-CNF) вычисляющей функцию чётности.

Четверг 23.11. С. Сперанский: "О теории истины по Крипке"

Speaker: 
С. Сперанский
Date: 
Thursday, November 23, 2017 - 17:20
Place: 
Институт философии СПбГУ (располагается по адресу: Менделеевская линия, дом 5), ауд. 27 (правая лестница, второй этаж)
Abstract: 

Сол Крипке в своей знаменитой статье (Kripke 1975) предложил собственный теоретико-модельный подход к теории истины. В рамках этого подхода роль допустимых (частичных) интерпретаций истинностного предиката T играют неподвижные точки специального рода монотонных операторов. Основой этих операторов являются различные схемы частичных означиваний, такие как схемы, соответствующие сильной или слабой трёхзначной логике Клини, или схема суперозначиваний ван Фраассена, а получающиеся в итоге наименьшие неподвижные точки представляют собой пределы специального рода трансфинитных последовательностей частичных интерпретаций. В настоящем докладе будет дан краткий обзор предложенного Крипке подхода и (при наличии времени) основных результатов в этом направлении.

Основная литература:
S. Kripke (1975). Outline of a theory of truth. Journal of Philosophy 72(19), 690–716.

Дополнительная литература:
S.O. Speranski (2017). Notes on the computational aspects of Kripke’s theory of truth. Studia Logica 105(2), 407–429.

Pages