ECCC-Report TR20-057https://eccc.weizmann.ac.il/report/2020/057Comments and Revisions published for TR20-057en-usSun, 26 Apr 2020 14:44:42 +0300
Paper TR20-057
| Polynomial Data Structure Lower Bounds in the Group Model |
Omri Weinstein,
Gleb Posobin,
Oded Regev,
Alexander Golovnev
https://eccc.weizmann.ac.il/report/2020/057Proving super-logarithmic data structure lower bounds in the static \emph{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.Sun, 26 Apr 2020 14:44:42 +0300https://eccc.weizmann.ac.il/report/2020/057