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 -