Семинары

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



Пятница 10.11. А. Смаль: "Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds"

Докладчик: 
А. Смаль
Дата: 
Friday, November 10, 2017 - 12:00
Место: 
402
Аннотация: 

Consider a random sequence of $n$ bits that has entropy at least n−k, where k<<n. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that says, roughly, that the average coordinate looks random to an adversary that is allowed to query ≈n/k other coordinates of the sequence, even if the adversary is non-deterministic. This setting generalizes decision trees and certificates for Boolean functions.

As an application of this result, we prove a new result on depth-3 circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (IPL 63(5), 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIDMA 3(2), 1990), and in particular it is a “top-down” proof (Hastad, Jukna and Pudlak, Computational Complexity 5(2), 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.



Пятница 10.11. А. Смаль: "Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds"

Докладчик: 
А. Смаль
Дата: 
Friday, November 10, 2017 - 12:00
Место: 
402
Аннотация: 

Доклад по статье: Or Meir, Avi Wigderson "Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds" (https://eccc.weizmann.ac.il/report/2017/149/).

Consider a random sequence of $n$ bits that has entropy at least $n−k$, where $k\ll n$. A commonly used observation is that an average coordinate of this random sequence is close to being uniformly distributed, that is, the coordinate “looks random”. In this work, we prove a stronger result that says, roughly, that the average coordinate looks random to an adversary that is allowed to query $\approx \frac{n}{k}$ other coordinates of the sequence, even if the adversary is non-deterministic. This setting generalizes decision trees and certificates for Boolean functions.

As an application of this result, we prove a new result on depth-3 circuits, which recovers as a direct corollary the known lower bounds for the parity and majority functions, as well as a lower bound on sensitive functions due to Boppana (IPL 63(5), 1997). An interesting feature of this proof is that it works in the framework of Karchmer and Wigderson (SIDMA 3(2), 1990), and in particular it is a “top-down” proof (Hastad, Jukna and Pudlak, Computational Complexity 5(2), 1995). Finally, it yields a new kind of a random restriction lemma for non-product distributions, which may be of independent interest.



Понедельник 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-разложимых графов.


Pages