"Arithmetic Data Structure Lower Bounds and Binary Compressed Sensing"
Omri Weinstein (Columbia)
Monday, February 8th 2021, 2-3pm
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^eps) lower bound for an explicit range counting problem of convex polygons in R^2 against linear-space 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 *binary* compressed sensing matrices in the polynomial sparsity regime (k=n1−). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.
joint work with Sasha Golovnev, Oded Regev, and Gleb Posobin