{"ID":2875590,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.02730","arxiv_id":"2509.02730","title":"Lower Bounds for Linear Operators","abstract":"We consider a static data structure problem of computing a linear operator under cell-probe model. Given a linear operator $M \\in \\mathbb{F}_2^{m \\times n}$, the goal is to pre-process a vector $X \\in \\mathbb{F}_2^n$ into a data structure of size $s$ to answer any query $\\langle M_i , X \\rangle$ in time $t$. We prove that for a random operator $M$, any such data structure requires: $$ t \\geq Ω( \\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 \\cdot \\log^{1/d}(n))$ for depth-$d$ circuits with arbitrary gates that compute a specific linear operator $M \\in \\mathbb{F}_2^{O(n) \\times 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^{n^{1/3}}$), and the total update time is $m^{0.99}$. Our result for the latter also applies to cases with super-polynomial $m$.","short_abstract":"We consider a static data structure problem of computing a linear operator under cell-probe model. Given a linear operator $M \\in \\mathbb{F}_2^{m \\times n}$, the goal is to pre-process a vector $X \\in \\mathbb{F}_2^n$ into a data structure of size $s$ to answer any query $\\langle M_i , X \\rangle$ in time $t$. We prove t...","url_abs":"https://arxiv.org/abs/2509.02730","url_pdf":"https://arxiv.org/pdf/2509.02730v1","authors":"[\"Young Kun Ko\"]","published":"2025-09-02T18:26:23Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\"]","methods":"[]","has_code":false}