TY - GEN

T1 - Polynomial data structure lower bounds in the group model

AU - Golovnev, Alexander

AU - Posobin, Gleb

AU - Regev, Oded

AU - Weinstein, Omri

N1 - Publisher Copyright:
© 2020 IEEE.

PY - 2020/11

Y1 - 2020/11

N2 - 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 mathbb{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 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.

AB - 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 mathbb{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 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.

KW - compressed sensing

KW - computational geometry

KW - data structures

KW - pseudorandomness

UR - http://www.scopus.com/inward/record.url?scp=85100349769&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85100349769&partnerID=8YFLogxK

U2 - 10.1109/FOCS46700.2020.00074

DO - 10.1109/FOCS46700.2020.00074

M3 - Conference contribution

AN - SCOPUS:85100349769

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 740

EP - 751

BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020

PB - IEEE Computer Society

T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020

Y2 - 16 November 2020 through 19 November 2020

ER -