Seminars http://algo.pdmi.ras.ru/tmpseminars en Понедельник 09.10. Дмитрий Юрьевич Григорьев (National Center for Scientific Research (CNRS), Institut des Mathématiques de Lille): "Тропическая комбинаторная теорема о нулях и тестирование малочленов" http://algo.pdmi.ras.ru/content/%D0%BF%D0%BE%D0%BD%D0%B5%D0%B4%D0%B5%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA-0910-%D0%B4%D0%BC%D0%B8%D1%82%D1%80%D0%B8%D0%B9-%D1%8E%D1%80%D1%8C%D0%B5%D0%B2%D0%B8%D1%87-%D0%B3%D1%80%D0%B8%D0%B3%D0%BE%D1%80%D1%8C%D0%B5%D0%B2-national-center-scientific-research-cnrs-institut <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>В начале предполагается привести базовые сведения о тропической<br /> алгебре, ее истоках и приложениях.<br /> Далее, обсудим следующие три направления результатов, недавно<br /> полученных совместно с В. Подольским.</p> <p>Первое, комбинаторную теорему о нулях Н. Алона и ее тропический аналог.</p> <p>Второе, лемму Шварца-Зиппеля о нулях на решетке, ее тропический аналог<br /> и приложения к вероятностному тестированию многочленов.</p></div></div></div> Wed, 30 Aug 2017 15:18:23 +0000 seminars 203 at http://algo.pdmi.ras.ru Пятница 06.10. Юрий Макарычев (Toyota Technological Institute at Chicago): "Алгоритмы для решения устойчивых задач комбинаторной оптимизации" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-0610-%D1%8E%D1%80%D0%B8%D0%B9-%D0%BC%D0%B0%D0%BA%D0%B0%D1%80%D1%8B%D1%87%D0%B5%D0%B2-toyota-technological-institute-chicago-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B-%D0%B4%D0%BB%D1%8F-%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D1%8F <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>Мы обсудим понятие устойчивости для задач комбинаторной оптимизации и кластеризации, предложенное Билу и Линиалом (2010). Задача называется α-устойчивой, если её оптимальное решение не меняется, когда мы немного изменяем её параметры (а именно умножаем каждый параметр на число между 1 и α). Мы расскажем об алгоритмах для решения стабильных задач комбинаторной оптимизации и кластеризации, таких как k-means, k-median, Max Cut, and Minimum Multiway Cut. Мы также представим несколько результатов о сложности решения стабильных задач.</p></div></div></div> Thu, 03 Aug 2017 18:49:47 +0000 seminars 202 at http://algo.pdmi.ras.ru Пятница 15.09. Калачев В.Н. (Минск): "К гипотезе Хартсфилда-Рингеля об антимагичности связных графов" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-1509-%D0%BA%D0%B0%D0%BB%D0%B0%D1%87%D0%B5%D0%B2-%D0%B2%D0%BD-%D0%BC%D0%B8%D0%BD%D1%81%D0%BA-%D0%BA-%D0%B3%D0%B8%D0%BF%D0%BE%D1%82%D0%B5%D0%B7%D0%B5-%D1%85%D0%B0%D1%80%D1%82%D1%81%D1%84%D0%B8%D0%BB%D0%B4%D0%B0-%D1%80%D0%B8%D0%BD%D0%B3%D0%B5%D0%BB%D1%8F-%D0%BE%D0%B1-%D0%B0%D0%BD%D1%82%D0%B8%D0%BC%D0%B0%D0%B3%D0%B8%D1%87%D0%BD%D0%BE%D1%81%D1%82%D0%B8-%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D1%85-%D0%B3%D1%80%D0%B0%D1%84-0 <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>Исследуется гипотеза Хартсфилда-Рингеля об антимагичности связных<br /> графов и возможность применения к ее доказательству методов<br /> алгебраической декомпозиции графов (АДГ).</p> <p>Основной результат – доказательство свойства антимагичности для<br /> (1,2)-полярных графов, (1,2)-разложимых графов, некоторых (1,Q)-полярных и (1,Q)-разложимых графов, а также униграфов. Основной идеей является применение результата М. Барруса, полученного для расщепляемых и 1-разложимых графов.</p> </div></div></div> Tue, 12 Sep 2017 11:11:00 +0000 seminars 206 at http://algo.pdmi.ras.ru Среда 12.07. Иван Михайлин: "Non-uniform lower bounds from uniform hardness assumptions" http://algo.pdmi.ras.ru/content/%D1%81%D1%80%D0%B5%D0%B4%D0%B0-1207-%D0%B8%D0%B2%D0%B0%D0%BD-%D0%BC%D0%B8%D1%85%D0%B0%D0%B9%D0%BB%D0%B8%D0%BD-non-uniform-lower-bounds-uniform-hardness-assumptions <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>In the talk we are going to discuss new connections between time and<br /> circuit complexities. While the approach is more or less generic, we<br /> will focus on the complete examples. We will prove that plausible<br /> assumption on time complexity of Max-3-SAT implies previously unknown<br /> circuit lower bounds. While this is interesting on it&#039;s own it also<br /> implies that proving that Max-3-SAT is SETH hard would give us some<br /> non-uniform lower bound as a side product. One appealing feature of</div></div></div> Wed, 05 Jul 2017 19:26:21 +0000 seminars 201 at http://algo.pdmi.ras.ru Пятница 02.06. Григорий Ярославцев (Indiana University Bloomington): "Linear Sketching using Parities" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-0206-%D0%B3%D1%80%D0%B8%D0%B3%D0%BE%D1%80%D0%B8%D0%B9-%D1%8F%D1%80%D0%BE%D1%81%D0%BB%D0%B0%D0%B2%D1%86%D0%B5%D0%B2-indiana-university-bloomington-linear-sketching-using <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>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.</div></div></div> Tue, 30 May 2017 10:14:32 +0000 seminars 199 at http://algo.pdmi.ras.ru Пятница 12.05. Alexei Miasnikov (Stevens Institute): "Hard instances, Dehn monsters, and complexity" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-1205-alexei-miasnikov-stevens-institute-hard-instances-dehn-monsters-and-complexity <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>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 &quot;hard&quot; 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.</p> </div></div></div> Wed, 10 May 2017 12:47:41 +0000 seminars 198 at http://algo.pdmi.ras.ru Пятница 21.04. Николай Мальковский (СПбГУ): "Распределенный алгоритм решения задачи о максимальном потоке" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-2104-%D0%BD%D0%B8%D0%BA%D0%BE%D0%BB%D0%B0%D0%B9-%D0%BC%D0%B0%D0%BB%D1%8C%D0%BA%D0%BE%D0%B2%D1%81%D0%BA%D0%B8%D0%B9-%D1%81%D0%BF%D0%B1%D0%B3%D1%83-%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9-%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D1%8F-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B8-%D0%BE-%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%BC <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>Задача о максимальном потоке и её двойственная -- задача о минимальном разрезе -- являются одними из наиболее изучаемых задач теории графов, на практике эти задачи часто встречаются в качестве промежуточных вычислений. В отдельных случаях возникает потребность решения задачи о максимальном потоке на вычислительной распределенной сети, где графом является топология взаимодействия этой сети. В таких ситуациях возникает вопрос: а можно ли решить задачу о максимальном потоке методом, не требующим синхронизации или сбора всей информации на одном из узлов сети?</div></div></div> Sat, 15 Apr 2017 20:13:06 +0000 seminars 197 at http://algo.pdmi.ras.ru Понедельник 17.04. А.Е. Ромащенко (LIRMM): "О геометрических и комбинаторных интерпретациях условных информационных неравенств" http://algo.pdmi.ras.ru/content/%D0%BF%D0%BE%D0%BD%D0%B5%D0%B4%D0%B5%D0%BB%D1%8C%D0%BD%D0%B8%D0%BA-1704-%D0%B0%D0%B5-%D1%80%D0%BE%D0%BC%D0%B0%D1%89%D0%B5%D0%BD%D0%BA%D0%BE-lirmm-%D0%BE-%D0%B3%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D1%85-%D0%B8-%D0%BA%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%BD%D1%8B%D1%85-%D0%B8%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D1%80%D0%B5%D1%82%D0%B0%D1%86%D0%B8%D1%8F%D1%85-%D1%83%D1%81%D0%BB%D0%BE%D0%B2%D0%BD%D1%8B%D1%85 <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>Следуя Н.Пиппенжеру, можно сказать, что наиболее общие &quot;законы теории информации&quot; выражаются в терминах линейных неравенств для энтропии Шеннона. Классические неравенства для энтропии (монотонность, субаддитивность, субмодулярность) восходят к работе К.Шеннона 1948 г. Эти неравенства имеют ясный интуитивный смысл. Например, субаддитивность энтропии $H(X,Y) \le H(X)+H(Y)$ означает, что &quot;количество информации&quot;, заключенное в паре случайных величин (X,Y), не превосходит суммы объемов информации в X и Y соответственно.</div></div></div> Tue, 11 Apr 2017 18:40:45 +0000 seminars 196 at http://algo.pdmi.ras.ru Пятница 07.04. А. Кноп: "Задача поиска и диаграммы принятия решений" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-0704-%D0%B0-%D0%BA%D0%BD%D0%BE%D0%BF-%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0-%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0-%D0%B8-%D0%B4%D0%B8%D0%B0%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D1%8B-%D0%BF%D1%80%D0%B8%D0%BD%D1%8F%D1%82%D0%B8%D1%8F-%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B9 <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>Классический результат Хватала и Семереди гласит, что размер древесного доказательства равен минимальному размеру дерева ищущему невыполненный клоз и аналогичное утверждение верно для регулярных резолюций и для 1-BP.</p> <p>Однако подобные результаты для более сложных классов диаграмм не были известны. В докладе мы рассмотрим системы доказательств похожие на систему доказательств IPS. Доказаны результаты об эквивалентности доказательств в этих системах и задач поиска невыполненного клоза, а так же доказаны нижние и верхние оценки в данных системах.</p> </div></div></div> Mon, 03 Apr 2017 12:31:40 +0000 seminars 195 at http://algo.pdmi.ras.ru Пятница 31.03. Станислав Сперанский (СПбГУ): "О сложности «элементарных» теорий различных классов вероятностных пространств" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-3103-%D1%81%D1%82%D0%B0%D0%BD%D0%B8%D1%81%D0%BB%D0%B0%D0%B2-%D1%81%D0%BF%D0%B5%D1%80%D0%B0%D0%BD%D1%81%D0%BA%D0%B8%D0%B9-%D1%81%D0%BF%D0%B1%D0%B3%D1%83-%D0%BE-%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8-%C2%AB%D1%8D%D0%BB%D0%B5%D0%BC%D0%B5%D0%BD%D1%82%D0%B0%D1%80%D0%BD%D1%8B%D1%85%C2%BB-%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B9-%D1%80%D0%B0%D0%B7%D0%BB%D0%B8%D1%87%D0%BD%D1%8B%D1%85-%D0%BA%D0%BB%D0%B0%D1%81%D1%81%D0%BE%D0%B2 <div class="field field-name-body field-type-text-with-summary field-label-hidden"><div class="field-items"><div class="field-item even" property="content:encoded"><p>Речь пойдёт об одном весьма естественном формальном языке для описания свойств вероятностных пространств. Этот язык содержит кванторы по событиям и (опционально) кванторы по вещественным числам, и в нём можно без труда выразить ряд основных свойств, таких как «быть дискретным (по модулю событий меры ноль)» или «быть безатомным». Мы поговорим об алгоритмической сложности теорий различных естественных классов вероятностных пространств в этом языке.</div></div></div> Fri, 24 Mar 2017 16:59:39 +0000 seminars 194 at http://algo.pdmi.ras.ru