Seminars

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



Среда 12.07. Иван Михайлин: "Non-uniform lower bounds from uniform hardness assumptions"

Speaker: 
Иван Михайлин
Date: 
Wednesday, July 12, 2017 - 12:00
Place: 
203
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.



Пятница 02.06. Григорий Ярославцев (Indiana University Bloomington): "Linear Sketching using Parities"

Speaker: 
Григорий Ярославцев (Indiana University Bloomington)
Date: 
Friday, June 2, 2017 - 17:15
Place: 
ауд. 203
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).



Пятница 12.05. Alexei Miasnikov (Stevens Institute): "Hard instances, Dehn monsters, and complexity"

Speaker: 
Alexei Miasnikov (Stevens Institute)
Date: 
Friday, May 12, 2017 - 18:00
Place: 
203
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.



Пятница 21.04. Николай Мальковский (СПбГУ): "Распределенный алгоритм решения задачи о максимальном потоке"

Speaker: 
Николай Мальковский (СПбГУ)
Date: 
Friday, April 21, 2017 - 17:15
Place: 
ауд. 203
Abstract: 

Задача о максимальном потоке и её двойственная -- задача о минимальном разрезе -- являются одними из наиболее изучаемых задач теории графов, на практике эти задачи часто встречаются в качестве промежуточных вычислений. В отдельных случаях возникает потребность решения задачи о максимальном потоке на вычислительной распределенной сети, где графом является топология взаимодействия этой сети. В таких ситуациях возникает вопрос: а можно ли решить задачу о максимальном потоке методом, не требующим синхронизации или сбора всей информации на одном из узлов сети? Алгоритмы, решающие какую-либо задачу в сети с такими ограничениями, обычно называются "распределенными". Как пример, задача синхронизации времени в сети допускает только распределенные методы решения. В докладе пойдет речь об одном распределенном алгоритме решения задачи о максимальном потоке и его связи с методами, основанными на электрических потоках и решении лапласиановых систем.



Понедельник 17.04. А.Е. Ромащенко (LIRMM): "О геометрических и комбинаторных интерпретациях условных информационных неравенств"

Speaker: 
А.Е. Ромащенко (LIRMM)
Date: 
Monday, April 17, 2017 - 17:00
Place: 
106
Abstract: 

Следуя Н.Пиппенжеру, можно сказать, что наиболее общие "законы теории информации" выражаются в терминах линейных неравенств для энтропии Шеннона. Классические неравенства для энтропии (монотонность, субаддитивность, субмодулярность) восходят к работе К.Шеннона 1948 г. Эти неравенства имеют ясный интуитивный смысл. Например, субаддитивность энтропии $H(X,Y) \le H(X)+H(Y)$ означает, что "количество информации", заключенное в паре случайных величин (X,Y), не превосходит суммы объемов информации в X и Y соответственно. Известны многочисленные применения информационных неравенств. Каждое линейное неравенство для энтропии можно эквивалентным образом переформулировать на многих разных языках: как утверждения о конечных группах, о колмогоровской сложности, о размерах проекций конечных множеств, и т.д.

Известны и более экзотические утверждения о шенноновской энтропии -- так называемые условные информационные неравенства (constraint information inequalities). Каждое такое неравенство выполнено при некотором ограничении на рассматриваемые случайные величины. Например, неравенство Инглетона для энтропий четверки случайных величин (A,B,C,D) выполняется при условии I(A:B) = I(A:B|C) = 0. Известно лишь несколько нетривиальных примеров условных информационных неравенств, и до недавнего времени они казались бессодержательными артефактами определения энтропии.

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


Pages