Polynomial Data Structure Lower Bounds in the Group Model

DOI10.1137/20M1381988zbMath1483.68462OpenAlexW3022083406MaRDI QIDQ5067444

Gleb Posobin, Omri Weinstein, Alexander Golovnev, Oded Regev

Publication date: 1 April 2022

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/20m1381988

zbMATH Keywords

data structurescomputational geometrycompressed sensingpseudorandomness

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• How hard is half-space range searching?
• Sharp bounds for vertical decompositions of linear arrangements in four dimensions
• On subspaces spanned by random selections of \(\pm 1\) vectors
• On range searching with semialgebraic sets
• Simplex range reporting on a pointer machine
• Random integral matrices: universality of surjectivity and the cokernel
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Pseudorandom Generators for Polynomial Threshold Functions
• Expander codes
• Lower bounds for orthogonal range searching: part II. The arithmetic model
• Euclidean Sections of $\ell_1^N$ with Sublinear Randomness and Error-Correction over the Reals
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Transdichotomous Results in Computational Geometry, I: Point Location in Sublogarithmic Time
• Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• A Lower Bound on the Complexity of Orthogonal Range Queries
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Simple Constructions of Almost k-wise Independent Random Variables
• Inequalities in Fourier Analysis on R ⁿ
• Multidimensional binary search trees used for associative searching
• Logarithmic Sobolev Inequalities
• Pseudorandomness via the Discrete Fourier Transform
• Simplex Range Searching and Its Variants: A Review
• On Universal Classes of Extremely Random Constant-Time Hash Functions
• Surjectivity of near-square random matrices
• Analysis of Boolean Functions
• Static data structure lower bounds imply rigidity
• LDPC Codes for Compressed Sensing
• Bounded Independence Fools Halfspaces
• On Range Searching with Semialgebraic Sets. II
• Quantum one-way communication can be exponentially stronger than classical communication
• On Range Searching in the Group Model and Combinatorial Discrepancy
• Class of constructive asymptotically good algebraic codes
• On a lemma of Littlewood and Offord

This page was built for publication: Polynomial Data Structure Lower Bounds in the Group Model