Lower Bounds for Linear Operators
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915476977745920 |
|---|---|
| author | Ko, Young Kun |
| author_facet | Ko, Young Kun |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02730 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Lower Bounds for Linear Operators Ko, Young Kun Computational Complexity Discrete Mathematics Data Structures and Algorithms 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$. |
| title | Lower Bounds for Linear Operators |
| topic | Computational Complexity Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.02730 |