文章基本信息

标题：Polynomial Data Structure Lower Bounds in the Group Model
本地全文：下载
作者：Alexander Golovnev ; Gleb Posobin ; Oded Regev 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2020
卷号：2020
页码：1-25
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 Ω(1)) lower bound for an explicit range counting problem of n 3 convex polygons in R 2 (each with n O˜(1) facets/semialgebraiccomplexity), 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−δ ). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.