Городской семинар по теории вероятностей и математической статистике, 12 октября 2018 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Городской семинар по теории вероятностей и математической статистике, 28 сентября 2018 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Петербургский топологический семинар им. В. А. Рохлина, 24 сентября 2018 г. 17:15, г. Санкт-Петербург, ПОМИ, комн. 203 (наб. р. Фонтанки, 27)

Городской семинар по теории вероятностей и математической статистике, 21 сентября 2018 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Пятница, 21 сентября, ауд. 106. Начало в 14:00.

Докладчик: Пётр Смирнов.

Тема: Сложность выполнимых и невыполнимых цейтинских формул для однопроходных ветвящихся программ.Abstract Классическая теория сложности изучает задачи распознавания: по входным данным необходимо выдать ответ «да» или «нет», то есть посчитать значение некоторой булевой функции. В теории сложности пропозициональных доказательств часто возникает задача поиска невыполненного дизъюнкта: по данной невыполнимой формуле в КНФ и подстановке значений переменных необходимо выдать какой-нибудь дизъюнкт формулы, который опровергается данной подстановкой. Мы рассмотрим однопроходные ветвящиеся программы (1-BP) и сравним для этой модели сложности двух естественных задач, связанных с цейтинскими формулами. Мы покажем, что задача вычисления значения выполнимой цейтинской формулы на графе G и задача поиска вершины, в которой нарушается условие четности, невыполнимой цейтинской формулы на графе G имеют близкую сложность для 1-BP. А именно, если минимальная программа для поиска вершины имеет размер S, то размер минимальной программы для вычисления значения имеет размер от S/n до S^O(log n), где n — число вершин в графе G.

Городской семинар по теории вероятностей и математической статистике, 14 сентября 2018 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Четверг, 6 сентября, ауд. 106. Начало в 14:00.

Докладчик: Владимир Лифшиц (University of Texas at Austin).

Тема: Стабильные модели формул исчисления высказываний.Abstract Понятие стабильной модели формулы исчисления высказываний служит основой новой формы декларативного программирования, которая часто применяется сегодня для решения переборных задач. Мы рассмотрим примеры программ этого типа, написанных в языке системы CLINGO, созданной в Потсдамском университете в Германии. Затем мы обсудим два конкурирующих определения стабильной модели, используемые разными группами программистов, и новые результаты, описывающие, при каких условиях эти определения эквивалентны.

Четверг, 6 сентября, ауд. 106. Начало в 14:00.

Докладчик: Владимир Лифшиц (University of Texas at Austin).

Тема: Стабильные модели формул исчисления высказываний.Abstract Понятие стабильной модели формулы исчисления высказываний служит основой новой формы декларативного программирования, которая часто применяется сегодня для решения переборных задач. Мы рассмотрим примеры программ этого типа, написанных в языке системы CLINGO, созданной в Потсдамском университете в Германии. Затем мы обсудим два конкурирующих определения стабильной модели, используемые разными группами программистов, и новые результаты, описывающие, при каких условиях эти определения эквивалентны.

Понедельник, 20 августа, ауд. 106. Начало в 14:00.

Докладчик: В.Е. Корепин (Stony Brook University).

Тема: Квантовый алгоритм поиска.Abstract Будет объяснен алгоритм Гровера и его приближенная версия.

Понедельник, 20 августа, ауд. 106. Начало в 14:00.

Докладчик: В.Е. Корепин (Stony Brook University).

Тема: Квантовый алгоритм поиска..Abstract Будет объяснен алгоритм Гровера и его приближенная версия.

Пятница, 20 июля, ауд. 203. Начало в 16:00.

Докладчик: Zhi-Wei Sun (Nanjing University).

Тема: Problems and Results on Sums of Squares.Abstract Due to the efforts of Fermat, Euler, Legendre and Gauss, it is known what
natural numbers can be written as the sum of two squares or three squares.
Lagrange's four-square theorem proved in 1770 states that each natural
number can be expressed as the sum of four squares.
In the talk we will first review classical results on sums of two or three
or four squares. Then we turn to the speaker's recent discoveries which
refine Lagrange's four-square theorem or the Gauss-Legendre theorem on
sums of three squares.
In particular we will introduce our results refining Lagrange's
four-square theorem as well as some recent conjectures of the speaker one
of which states that any integer greater than one can be written as the
sum of two squares, a power of 3 and a power of 5.

Городской семинар по теории вероятностей и математической статистике, 16 июля 2018 г. 15:30, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Пятница, 13 июля, 203. Начало в 13:30.

Докладчик: Д. Соколов.

Тема: От доказательств к вычислениям.Abstract Монотонные Span Programs (mSP) были предложены Карчмером и Вигдерсоном в начале 90-х годов, позднее было
доказано, что они моделируют монотонные булевы формулы. Также известно квазиполиномиальное разделение между
mSP над полем F_2 и монотонными схемами.

Пользуясь недавними теоремами о лифтинге мы покажем, что задача о разделении данных моделей вычислений следует из разделения резолюционной системы доказательств и Nullstellensatz. Мы предъявим экспоненциальное разделение данных систем.

Четверг, 12 июля, 203. Начало в 18:00.

Докладчик: А. Кноп.

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

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

Городской семинар по теории вероятностей и математической статистике, 29 июня 2018 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Вторник, 19 июня, 402. Начало в 12:00.

Докладчик: Navid Talebanfard (Institute of Mathematics of the Czech Academy of Sciences).

Тема: Structure in Proof Complexity: The Case of Tseitin and Tree Decompositions.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.

Городской семинар по теории вероятностей и математической статистике, 8 июня 2018 г. 18:00, г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

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

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

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