Seminars http://algo.pdmi.ras.ru/tmpseminars en Пятница 15.12. А. Смаль: "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-1512-%D0%B0-%D1%81%D0%BC%D0%B0%D0%BB%D1%8C-ppsz-general-k-sat-making-hertlis-analysis-simpler-and-3-sat-faster <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>Доклад по статье Dominik Scheder, John Steinberger &quot;PPSZ for General k-SAT - Making Hertli&#039;s Analysis Simpler and 3-SAT Faster&quot; (<a href="http://drops.dagstuhl.de/opus/volltexte/2017/7535/">http://drops.dagstuhl.de/opus/volltexte/2017/7535/</a>)</p> <p>В докладе будет представлено простое изложение статьи Хертли о PPSZ. Кроме того будет показано, что если мы улучшим PPSZ для Unique-k-SAT, то из этого получится улучшение для обычного k-SAT (но с худшими параметрами).</p> </div></div></div> Mon, 11 Dec 2017 21:25:08 +0000 seminars 227 at http://algo.pdmi.ras.ru Понедельник 11.12. Смаль А.: "PPZ lowerbound via entropy" 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-1112-%D1%81%D0%BC%D0%B0%D0%BB%D1%8C-%D0%B0-ppz-lowerbound-entropy <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>На семинаре мы рассмотрим простое доказательство основной теоремы из статьи Or Meir, Avi Wigderson &quot;Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds&quot; (<a href="https://eccc.weizmann.ac.il/report/2017/149/">https://eccc.weizmann.ac.il/report/2017/149/</a>), а точнее её более сильной версии. Кроме того, будет показано, как из этой более сильной теоремы следует нижняя оценка 2^(n/k - 1) на размер схемы глубины 3 (OR-k-CNF) вычисляющей функцию чётности.</p> </div></div></div> Wed, 06 Dec 2017 15:33:10 +0000 seminars 226 at http://algo.pdmi.ras.ru Четверг 23.11. С. Сперанский: "О теории истины по Крипке" http://algo.pdmi.ras.ru/content/%D1%87%D0%B5%D1%82%D0%B2%D0%B5%D1%80%D0%B3-2311-%D1%81-%D1%81%D0%BF%D0%B5%D1%80%D0%B0%D0%BD%D1%81%D0%BA%D0%B8%D0%B9-%D0%BE-%D1%82%D0%B5%D0%BE%D1%80%D0%B8%D0%B8-%D0%B8%D1%81%D1%82%D0%B8%D0%BD%D1%8B-%D0%BF%D0%BE-%D0%BA%D1%80%D0%B8%D0%BF%D0%BA%D0%B5 <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>Сол Крипке в своей знаменитой статье (Kripke 1975) предложил собственный теоретико-модельный подход к теории истины. В рамках этого подхода роль допустимых (частичных) интерпретаций истинностного предиката T играют неподвижные точки специального рода монотонных операторов.</div></div></div> Thu, 09 Nov 2017 07:29:42 +0000 seminars 224 at http://algo.pdmi.ras.ru Пятница 10.11. А. Смаль: "Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-1011-%D0%B0-%D1%81%D0%BC%D0%B0%D0%BB%D1%8C-prediction-partial-information-and-hindsight-application-circuit-lower <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>Consider a random sequence of $n$ bits that has entropy at least n−k, where k&lt;&lt;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.</p></div></div></div> Mon, 06 Nov 2017 18:04:55 +0000 seminars 222 at http://algo.pdmi.ras.ru Пятница 10.11. А. Смаль: "Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds" http://algo.pdmi.ras.ru/content/%D0%BF%D1%8F%D1%82%D0%BD%D0%B8%D1%86%D0%B0-1011-%D0%B0-%D1%81%D0%BC%D0%B0%D0%BB%D1%8C-prediction-partial-information-and-hindsight-application-circuit-lowe-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>Доклад по статье: Or Meir, Avi Wigderson &quot;Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds&quot; (<a href="https://eccc.weizmann.ac.il/report/2017/149/">https://eccc.weizmann.ac.il/report/2017/149/</a>).</p></div></div></div> Mon, 06 Nov 2017 18:14:57 +0000 seminars 223 at http://algo.pdmi.ras.ru Понедельник 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