2025/09/02 by Ko, Young Kun
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2509.02730
We consider a static data structure problem of computing a linear operator under cell-probe model. Given a linear operator M ∈ \mathbbF2m × n, the goal is to pre-process a vector X ∈ \mathbbF2n into a data structure of size s to answer any query ⟨ Mi , X ⟩ in time t. We prove that for a random operator M, any such data structure requires: t ≥ Ω( min \ log (m/s) , n / log s \ ). This result overcomes the well-known logarithmic barrier in static data structures [MNSW98, Sie04, PD06, PTW08, Pat11, DGW19] by using a random linear operator. Furthermore, it provides the first significant progress toward confirming a decades-old folklore conjecture: that non-linear pre-processing does not substantially help in computing most linear operators. A straightforward modification of our proof also yields a wire lower bound of Ω(n ⋅ log1/d(n)) for depth-d circuits with arbitrary gates that compute a specific linear operator M ∈ \mathbbF2O(n) × n, even against some small constant advantage over random guessing. This bound holds even for circuits with only a small constant advantage over random guessing, improving upon longstanding results [RS03, Che08a, Che08b, GHK+13] for a random operator. Finally, our work partially resolves the communication form of the Multiphase Conjecture [Pat10] and makes progress on Jukna-Schnitger's Conjecture [JS11, Juk12]. We address the former by considering the Inner Product (mod 2) problem (instead of Set Disjointness) when the number of queries m is super-polynomial (e.g., 2^n1/3), and the total update time is m0.99. Our result for the latter also applies to cases with super-polynomial m.