Семинары

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


Пятница 22.12. Д.О. Соколов: "Monotone Circuit Lower Bounds from Resolution"

Докладчик: 
Д.О. Соколов
Дата: 
Friday, December 22, 2017 - 13:00
Место: 
402
Аннотация: 

Для любой формулы, которая сложна для резолюций, мы покажем что если заменить каждую переменную на функцию индексирования от новых переменных, то получится формула, которая является сложной для любой
семантической системы доказательств, строки которой могут быть вычислены эффективным коммуникационным протоколом (CP^*, CP, ...).

Данный результат представляет собой так называемую "lifting theorem" для графа запросов и коммуникационных протоколов на графах.

Доклад по совместной работе с Ankit Garg, Mika Göös и Pritish Kamath.

Внимание! Ориентировочная продолжительность доклада 2 пары: с 13-00 до 14-40 и с 16-00 до 17-40.

Пятница 15.12. А. Смаль: "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster"

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

Доклад по статье Dominik Scheder, John Steinberger "PPSZ for General k-SAT - Making Hertli's Analysis Simpler and 3-SAT Faster" (http://drops.dagstuhl.de/opus/volltexte/2017/7535/)

В докладе будет представлено простое изложение статьи Хертли о PPSZ. Кроме того будет показано, что если мы улучшим PPSZ для Unique-k-SAT, то из этого получится улучшение для обычного k-SAT (но с худшими параметрами).

Понедельник 11.12. Смаль А.: "PPZ lowerbound via entropy"

Докладчик: 
Смаль А.
Дата: 
Monday, December 11, 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/), а точнее её более сильной версии. Кроме того, будет показано, как из этой более сильной теоремы следует нижняя оценка 2^(n/k - 1) на размер схемы глубины 3 (OR-k-CNF) вычисляющей функцию чётности.

Четверг 23.11. С. Сперанский: "О теории истины по Крипке"

Докладчик: 
С. Сперанский
Дата: 
Thursday, November 23, 2017 - 17:20
Место: 
Институт философии СПбГУ (располагается по адресу: Менделеевская линия, дом 5), ауд. 27 (правая лестница, второй этаж)
Аннотация: 

Сол Крипке в своей знаменитой статье (Kripke 1975) предложил собственный теоретико-модельный подход к теории истины. В рамках этого подхода роль допустимых (частичных) интерпретаций истинностного предиката T играют неподвижные точки специального рода монотонных операторов. Основой этих операторов являются различные схемы частичных означиваний, такие как схемы, соответствующие сильной или слабой трёхзначной логике Клини, или схема суперозначиваний ван Фраассена, а получающиеся в итоге наименьшие неподвижные точки представляют собой пределы специального рода трансфинитных последовательностей частичных интерпретаций. В настоящем докладе будет дан краткий обзор предложенного Крипке подхода и (при наличии времени) основных результатов в этом направлении.

Основная литература:
S. Kripke (1975). Outline of a theory of truth. Journal of Philosophy 72(19), 690–716.

Дополнительная литература:
S.O. Speranski (2017). Notes on the computational aspects of Kripke’s theory of truth. Studia Logica 105(2), 407–429.

Пятница 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.

Pages