Пятница, 25 сентября, Zoom. Начало в 18:00.
Докладчик: Alexander Golovnev (Georgetown University, USA).
Тема: Polynomial Data Structure Lower Bounds in the Group Model.
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)} $](../../../sites/default/files/tex/eb0f182973f61d42f0302bf04254f6ea794714ed/index.png)
) lower bound for an explicit range counting problem of
![$ n^3 $](../../../sites/default/files/tex/cf577ab2ec559811ae9ca8706e7f4dd647850aed/index.png)
convex polygons in
![$ \mathbb{R}^2 $](../../../sites/default/files/tex/ef7bfa246e7fe4a7c44684c36faac1fc851351e4/index.png)
(each with
![$ n^{\tilde{O}(1)} $](../../../sites/default/files/tex/1213b4f8f1438b24c5a58085439cfe47273391c0/index.png)
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} $](../../../sites/default/files/tex/b787ae6381ce0225c2ef4d1bea4417098fb232db/index.png)
). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.
The talk is based on the following paper:
https://eccc.weizmann.ac.il/report/2020/057/
Видео доклада:
https://www.youtube.com/watch?v=lQDYSOUBRP8