Пятница, 6 октября, ПОМИ РАН, ауд. 106. Начало в 18:00.

Докладчик: Юрий Макарычев (Toyota Technological Institute at Chicago).

Тема: Алгоритмы для решения устойчивых задач комбинаторной оптимизации.Abstract Мы обсудим понятие устойчивости для задач комбинаторной оптимизации и кластеризации, предложенное Билу и Линиалом (2010). Задача называется α-устойчивой, если её оптимальное решение не меняется, когда мы немного изменяем её параметры (а именно умножаем каждый параметр на число между 1 и α). Мы расскажем об алгоритмах для решения стабильных задач комбинаторной оптимизации и кластеризации, таких как k-means, k-median, Max Cut, and Minimum Multiway Cut. Мы также представим несколько результатов о сложности решения стабильных задач.

Доклад основан на совместных работах с Харисом Анджелидакисом, Аравинданом Виджейарагаваном и Константином Макарычевым.

Пятница, 6 октября, ПОМИ РАН, ауд. 106. Начало в 18:00.

Докладчик: Юрий Макарычев (Toyota Technological Institute at Chicago).

Тема: Алгоритмы для решения устойчивых задач комбинаторной оптимизации.Abstract Мы обсудим понятие устойчивости для задач комбинаторной оптимизации и кластеризации, предложенное Билу и Линиалом (2010). Задача называется α-устойчивой, если её оптимальное решение не меняется, когда мы немного изменяем её параметры (а именно умножаем каждый параметр на число между 1 и α). Мы расскажем об алгоритмах для решения стабильных задач комбинаторной оптимизации и кластеризации, таких как k-means, k-median, Max Cut, and Minimum Multiway Cut. Мы также представим несколько результатов о сложности решения стабильных задач.

Доклад основан на совместных работах с Харисом Анджелидакисом, Аравинданом Виджейарагаваном и Константином Макарычевым.

Пятница, 6 октября, ПОМИ РАН, ауд. 106. Начало в 18:00.

Докладчик: Юрий Макарычев (Toyota Technological Institute at Chicago).

Тема: Алгоритмы для решения устойчивых задач комбинаторной оптимизации.Abstract Мы обсудим понятие устойчивости для задач комбинаторной оптимизации и кластеризации, предложенное Билу и Линиалом (2010). Задача называется α-устойчивой, если её оптимальное решение не меняется, когда мы немного изменяем её параметры (а именно умножаем каждый параметр на число между 1 и α). Мы расскажем об алгоритмах для решения стабильных задач комбинаторной оптимизации и кластеризации, таких как k-means, k-median, Max Cut, and Minimum Multiway Cut. Мы также представим несколько результатов о сложности решения стабильных задач.

Доклад основан на совместных работах с Харисом Анджелидакисом, Аравинданом Виджейарагаваном и Константином Макарычевым.

Cреда, 12 июля, 203. Начало в 12:00.

Докладчик: Иван Михайлин.

Тема: Non-uniform lower bounds from uniform hardness assumptions.Abstract In the talk we are going to discuss new connections between time and
circuit complexities. While the approach is more or less generic, we
will focus on the complete examples. We will prove that plausible
assumption on time complexity of Max-3-SAT implies previously unknown
circuit lower bounds. While this is interesting on it's own it also
implies that proving that Max-3-SAT is SETH hard would give us some
non-uniform lower bound as a side product. One appealing feature of
this approach is that Max-3-SAT being SETH hard would be consistent
with current knowledge.

Cреда, 12 июля, 203. Начало в 12:00.

Докладчик: Иван Михайлин.

Тема: Non-uniform lower bounds from uniform hardness assumptions.Abstract In the talk we are going to discuss new connections between time and
circuit complexities. While the approach is more or less generic, we
will focus on the complete examples. We will prove that plausible
assumption on time complexity of Max-3-SAT implies previously unknown
circuit lower bounds. While this is interesting on it's own it also
implies that proving that Max-3-SAT is SETH hard would give us some
non-uniform lower bound as a side product. One appealing feature of
this approach is that Max-3-SAT being SETH hard would be consistent
with current knowledge.

Cреда, 28 июня, 203. Начало в 12:00.

Докладчик: Navid Talebanfard (Saarland University and the Cluster of Excellence, MMCI).

Тема: Tighter Hard Instances for PPSZ.Abstract We construct uniquely satisfiable k-CNF formulas that are hard for the algorithm PPSZ. Firstly, we construct graph-instances on which "weak PPSZ" has savings of at most (2+ϵ)/k; the saving of an algorithm on an input formula with n variables is the largest γ such that the algorithm succeeds (i.e. finds a satisfying assignment) with probability at least 2−(1−γ)n. Since PPSZ (both weak and strong) is known to have savings of at least π2+o(1)6k, this is optimal up to the constant factor. In particular, for k=3, our upper bound is 20.333…n, which is fairly close to the lower bound 20.386…n of Hertli [SIAM J. Comput.'14]. We also construct instances based on linear systems over F2 for which strong PPSZ has savings of at most O(log(k)k). This is only a log(k) factor away from the optimal bound. Our constructions improve previous savings upper bound of O(log2(k)k) due to Chen et al. [SODA'13].

https://arxiv.org/abs/1611.01291

Пятница, 2 июня, ауд. 203. Начало в 17:15.

Докладчик: Григорий Ярославцев (Indiana University Bloomington).

Тема: Linear Sketching using Parities.Abstract Linear sketching is a data compression technique based on computing a small number of linear functions over the data. With careful choice of such functions one can perform various computations of interest later only looking at their values and not the data itself. In the recent years linear sketching has emerged as a powerful tool for approximate computing in settings with limited resources including distributed computation and streaming. It has been used in breakthrough results on graph and matrix processing, dimensionality reduction, etc. Strikingly, linear sketches have been shown to be optimal for dynamic stream processing under fairly mild assumptions.

In this talk I will describe a new study of linear sketching that focuses on understanding the power of linear sketches based on parities (i.e. over GF_2, the field of two elements, as compared to the previous work that uses real arithmetic). I will illustrate various properties of such sketches using Fourier-analytic methods and tools from communication complexity. In particular, linear sketching over GF_2 turns out to be closely related to Fourier sparsity with respect to Lp-norms. Moreover, it can be shown to be optimal in streaming and distributed settings for data generated according to the uniform distribution.

Joint work with Sampath Kannan (UPenn) and Elchanan Mossel (MIT) and Swagato Sanyal (TIFR).

Пятница, 2 июня, ауд. 203. Начало в 17:15.

Докладчик: Григорий Ярославцев (Indiana University Bloomington).

Тема: Linear Sketching using Parities.Abstract Linear sketching is a data compression technique based on computing a small number of linear functions over the data. With careful choice of such functions one can perform various computations of interest later only looking at their values and not the data itself. In the recent years linear sketching has emerged as a powerful tool for approximate computing in settings with limited resources including distributed computation and streaming. It has been used in breakthrough results on graph and matrix processing, dimensionality reduction, etc. Strikingly, linear sketches have been shown to be optimal for dynamic stream processing under fairly mild assumptions.

In this talk I will describe a new study of linear sketching that focuses on understanding the power of linear sketches based on parities (i.e. over GF_2, the field of two elements, as compared to the previous work that uses real arithmetic). I will illustrate various properties of such sketches using Fourier-analytic methods and tools from communication complexity. In particular, linear sketching over GF_2 turns out to be closely related to Fourier sparsity with respect to Lp-norms. Moreover, it can be shown to be optimal in streaming and distributed settings for data generated according to the uniform distribution.

Joint work with Sampath Kannan (UPenn) and Elchanan Mossel (MIT) and Swagato Sanyal (TIFR).

Knot exterior with all possible meridional essential surfaces
J. M. Nogueira
29 мая 2017 г. 17:15
г. Санкт-Петербург, ПОМИ, комн. 203 (наб. р. Фонтанки, 27)

Пространство когерентных пар точек
А. А. Куделькин
22 мая 2017 г. 18:15
г. Санкт-Петербург, ПОМИ, комн. 203 (наб. р. Фонтанки, 27)

Многогранник Лавренченко
М. В. Петров
22 мая 2017 г. 17:15
г. Санкт-Петербург, ПОМИ, комн. 203 (наб. р. Фонтанки, 27)

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 25 мая 2017, 16:00Место: комната 203Докладчик: А. Л. Вернер, М. Н. Васильева, О. Г. Данилова. (РГПУ)Тема: Наглядная геометрия многогранников Кеплера - Пуансо (от Коксетера к Александрову)Аннотация: 

Рассказывается о таких понятиях, как сферическое изображение
звёздчатого многогранника, его развёртка, внутренняя метрика,
кривизна, разрезывание и склеивание, о которых в работах Коксетера и
его школы не говорилось.

О точной асимптотике малых уклонений $L_2$-норм некоторых гауссовских случайных полей
Л. В. Розовский
19 мая 2017 г. 18:00
г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 18 мая 2017, 16:00Место: комната 203Докладчик: Ю. Белоусов (СПбГУ)Тема: Семейство новых инвариантов классических узловАннотация: 

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

Функториальные разложения спектральной последовательности Кёртиса
Ф. Ю. Павутницкий
15 мая 2017 г. 17:15
г. Санкт-Петербург, ПОМИ, комн. 203 (наб. р. Фонтанки, 27)

Slow movement of biased walks on trees
Zh. Shi
12 мая 2017 г. 18:00
г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)

Пятница, 12 мая, 203. Начало в 18:00.

Докладчик: Alexei Miasnikov (Stevens Institute).

Тема: Hard instances, Dehn monsters, and complexity.Abstract In this talk I will focus on two seemingly different directions in modern algorithmic group theory: finding more and more efficient algorithms and how to find "hard" instances of the problems, how to amplify hardness, and how to measure hardness of the algorithms. The talk is intended to be non-technical, I will emphasize some relations between algorithmic group theory and cryptography.

Пятница, 12 мая, 203. Начало в 18:00.

Докладчик: Alexei Miasnikov (Stevens Institute).

Тема: Hard instances, Dehn monsters, and complexity.Abstract In this talk I will focus on two seemingly different directions in modern algorithmic group theory: finding more and more efficient algorithms and how to find "hard" instances of the problems, how to amplify hardness, and how to measure hardness of the algorithms. The talk is intended to be non-technical, I will emphasize some relations between algorithmic group theory and cryptography.

Семинар: Петербургский геометрический семинар им. А.Д.АлександроваВремя: четверг, 11 мая 2017, 16:00Место: комната 203Докладчик: С. В. Иванов (ПОМИ)Тема: Геодезические потоки финслеровых метрик постоянной положительной кривизныАннотация: 

Флаговая кривизна финслерова многообразия -- обобщение римановой секционной кривизны.
В отличие от риманова случая, существуют нестандартные финслеровы метрики постоянной
флаговой кривизны. Я расскажу классификацию геодезических потоков (с точностью до сопряжения)
таких метрик на двумерной сфере: тип геодезического потока определяется длиной
кратчайшей замкнутой геодезической, которая может принимать любое значение из
интервала $(\pi,2\pi]$. По совместной работе с R.Bryant, P.Foulon, V.Matveev и W.Ziller.

Вероятность поглощения для гауссовского политопа и правильные сферические симплексы.
Д. Н. Запорожец
5 мая 2017 г. 18:00
г. Санкт-Петербург, ПОМИ, ауд. 311 (наб. р. Фонтанки, 27)