Derandomization of Cell Sampling

2021/08/12 by Alexander Golovnev, Tom Gur, Golovnev, Alexander +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · #Cell Image Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.2108.05970

openalex publication_date 2021/08/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Since 1989, the best known lower bound on static data structures was Siegel's classical cell sampling lower bound. Siegel showed an explicit problem with n inputs and m possible queries such that every data structure that answers queries by probing t memory cells requires space s≥\widetildeΩ(n⋅((m)/(n))^1/t). In this work, we improve this bound for non-adaptive data structures to s≥\widetildeΩ(n⋅((m)/(n))^1/(t-1)) for all t ≥ 2. For t=2, we give a lower bound of s>m-o(m), improving on the bound s>m/2 recently proved by Viola over \mathbbF₂ and Siegel's bound s≥\widetildeΩ(√(mn)) over other finite fields.

Cited by

• Cell-Probe Lower Bounds via Semi-Random CSP Refutation: Simplified and the Odd-Locality Case

Related

• Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds
• Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
• Sampling Permutations with Cell Probes is Hard
• Logarithmic Lower Bounds in the Cell-Probe Model
• Tight Static Lower Bounds for Non-Adaptive Data Structures