All reports by Author Gleb Posobin:

__
TR20-057
| 20th April 2020
__

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein#### Polynomial Data Structure Lower Bounds in the Group Model

Revisions: 1

Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein

Proving 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 ... more >>>