Seminars

Mailing list: https://groups.google.com/forum/#!forum/spb-algo



Среда 07.10. Анастасия Софронова: "Нижние оценки на задачи поиска для (1, +k)-ветвящихся программ"

Speaker: 
Анастасия Софронова
Date: 
Wednesday, October 7, 2020 - 18:00
Place: 
Zoom (обратите внимание на нестандартный день семинара!)
Abstract: 

В докладе мы докажем нижнюю оценку на задачу поиска невыполненного клоза для ветвящихся программ с ограниченным числом повторений переменных; а именно, нижнюю оценку $2^\Omega(n/k^2)$ для семейства формул $f_n$ размера poly(n) и $k = O(\log n/ \log \log n)$, где k — число повторений переменных. Семейство формул представляет собой некоторую модификацию невыполнимых формул, кодирующих существование линейного порядка без минимума на множестве из n элементов.

Ссылка на Zoom будет отправлена на рассылку семинара за пару часов до начала доклада.



Пятница 02.10. Пётр Смирнов: "Квазиполиномиальные опровержения цейтинских формул в Cutting Planes"

Speaker: 
Пётр Смирнов
Date: 
Friday, October 2, 2020 - 18:00
Place: 
Zoom
Abstract: 

В докладе для любой цейтинской невыполнимой формулы на графе G мы построим опровержение в системе Cutting Planes (CP) длины $2^D (nD)^O(log n)$, где n — число вершин графа G, а D — его максимальная степень.

Опровержение строится следующим образом: мы рассматриваем (построенное ранее в другой работе) квазиполиномиальное опровержение в более сильной системе Stabbing Planes, замечаем структурное свойство этого опровержения, а затем перестраиваем любое опроверждение с таким свойством в систему CP.

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

Доклад основан на статье Daniel Dadush и Samarth Tiwari «On the Complexity of Branching Proofs» [https://homepages.cwi.nl/~dadush/papers/branching.pdf].

Ссылка на конференцию Zoom будет отправлена за пару часов до доклада.



Пятница 25.09. Alexander Golovnev (Georgetown University, USA): "Polynomial Data Structure Lower Bounds in the Group Model"

Speaker: 
Alexander Golovnev (Georgetown University, USA)
Date: 
Friday, September 25, 2020 - 18:00
Place: 
Zoom
Abstract: 

Proving super-logarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early 80's. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\R^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic-complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing---in particular, on the existence and partial derandomization of optimal \emph{binary} compressed sensing matrices in the polynomial sparsity regime ($k = n^{1-\delta}$). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.



Пятница 04.09. Александр Смаль (ПОМИ): "Гипотеза XOR-KRW"

Speaker: 
Александр Смаль (ПОМИ)
Date: 
Friday, September 4, 2020 - 18:00
Place: 
Zoom
Abstract: 

Доклад по статье Ivan Mihajlin, Alexander Smal, "Toward better depth lower bounds: the XOR-KRW conjecture" https://eccc.weizmann.ac.il/report/2020/116/

В этом докладе будет рассказано про новую гипотеза XOR-KRW, которая является ослаблением гипотезы Карчмера-Раза-Вигдерсона [KRW95]. Не смотря на то, что эта гипотеза более слабая, чем гипотеза KRW, из её доказательства будет следовать, что $P\not\subseteq NC_1$. Кроме того, будет сформулировано ослабление XOR-KRW гипотезы, доказательство которой повлечёт суперкубическую нижнюю оценку на формульную сложность в базисе Де Моргана.

Изучение этой гипотезы позволило нам частично ответить на открытый вопрос, сформулированный в статье Гавинского и др. [GMWW17] касательно композиции универсального отношения и функции. Если быть более точным, то мы покажем, что существует функция $g$, такая что композиция универсального отношения и $g$ значительно сложнее, чем универсальное отношение. Тот факт, что мы можем доказать лишь факт существование $g$ является неотъемлемой чертой нашего подхода.

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



Пятница 28.08. Артур Игнатьев (СПбГУ): "Новые оценки на полудуплексную коммуникационную сложность"

Speaker: 
Артур Игнатьев (СПбГУ)
Date: 
Friday, August 28, 2020 - 18:00
Place: 
Zoom
Abstract: 

В докладе будет рассказываться про новые оценки на коммуникационную сложность в полудуплексной модели коммуникации. Полудуплексная коммуникационная модель - это обобщение классической модели коммуникационной сложности, предложенной Яо. Общение в такой полудуплексной модели напоминает общение по рации: в каждый момент времени каждый игрок находится либо в состоянии передачи сообщения, либо в состоянии приёма. При этом, если оба игрока передают сообщение одновременно, то они не слышат друг друга, а сообщения теряются. Мотивация для изучения данной модели происходит из исследований KRW гипотезы для композиции функции и мультиплексера. В докладе будет рассказано о новых верхних и нижних оценках для функции $DISJ_n$, а также для игр Карчмера-Вигдерсона для функций подсчёта по модулю и рекурсивной функции большинства. Кроме того, будет сформулировано определение недетерминированной полудуплексной коммуникационной сложности и доказаны оценки, связывающие её с классической недетерминированной коммуникационной сложностью.

По материалам статьи: Yuriy Dementiev, Artur Ignatiev, Vyacheslav Sidelnik, Alexander Smal, Mikhail Ushakov, "New bounds on the half-duplex communication complexity" (https://eccc.weizmann.ac.il/report/2020/117/)

Семинар будет проходить онлайн в конференции zoom. Ссылка для подключения будет выслана в рассылку за пару часов до доклада.


Pages