Семинары

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



Понедельник 09.10. Дмитрий Юрьевич Григорьев (National Center for Scientific Research (CNRS), Institut des Mathématiques de Lille): "Тропическая комбинаторная теорема о нулях и тестирование малочленов"

Докладчик: 
Дмитрий Юрьевич Григорьев (National Center for Scientific Research (CNRS), Institut des Mathématiques de Lille)
Дата: 
Monday, October 9, 2017 - 18:00
Место: 
ПОМИ, ауд. 106
Аннотация: 

В начале предполагается привести базовые сведения о тропической
алгебре, ее истоках и приложениях.
Далее, обсудим следующие три направления результатов, недавно
полученных совместно с В. Подольским.

Первое, комбинаторную теорему о нулях Н. Алона и ее тропический аналог.

Второе, лемму Шварца-Зиппеля о нулях на решетке, ее тропический аналог
и приложения к вероятностному тестированию многочленов.

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



Пятница 06.10. Юрий Макарычев (Toyota Technological Institute at Chicago): "Алгоритмы для решения устойчивых задач комбинаторной оптимизации"

Докладчик: 
Юрий Макарычев (Toyota Technological Institute at Chicago)
Дата: 
Friday, October 6, 2017 - 18:00
Место: 
ПОМИ РАН, ауд. 106
Аннотация: 

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

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



Пятница 15.09. Калачев В.Н. (Минск): "К гипотезе Хартсфилда-Рингеля об антимагичности связных графов"

Докладчик: 
Калачев В.Н. (Минск)
Дата: 
Friday, September 15, 2017 - 17:15
Место: 
ауд. 203
Аннотация: 

Исследуется гипотеза Хартсфилда-Рингеля об антимагичности связных
графов и возможность применения к ее доказательству методов
алгебраической декомпозиции графов (АДГ).

Основной результат – доказательство свойства антимагичности для
(1,2)-полярных графов, (1,2)-разложимых графов, некоторых (1,Q)-полярных и (1,Q)-разложимых графов, а также униграфов. Основной идеей является применение результата М. Барруса, полученного для расщепляемых и 1-разложимых графов.



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

Докладчик: 
Иван Михайлин
Дата: 
Wednesday, July 12, 2017 - 12:00
Место: 
203
Аннотация: 

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"

Докладчик: 
Григорий Ярославцев (Indiana University Bloomington)
Дата: 
Friday, June 2, 2017 - 17:15
Место: 
ауд. 203
Аннотация: 

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).


Pages