Lower Bounds for Linear Operators
Young Kun Ko · 2025
Read Lower Bounds for Linear Operators by Young Kun Ko (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02730.txt.
Introduction
Young Kun Ko wrote a 2025 solo theoretical computer science paper proving lower bounds for data structures that compute linear operators. A vector is preprocessed once, then inner product queries against rows of a fixed matrix must be answered quickly from a small structure.
For a random binary matrix, Ko proves any such structure needs query time growing with a stated minimum of two quantities. The bound breaks a long-standing logarithmic barrier for static data structures. It also gives the first major progress toward a folklore conjecture that nonlinear preprocessing barely helps for most linear operators. Variants yield stronger circuit lower bounds for a specific operator, plus progress on the multiphase and Jukna-Schnitger conjectures. Randomness of the operator is the key that unlocks the argument.
Catalog record
| CREATOR | Young Kun Ko |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-02730
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Lower Bounds for Linear Operators Young Kun Ko Abstract We consider a static data structure problem of computing a linear operator under cell-probe model. Given a linear operator M ∈ 𝔽 2 m × n M\in\mathbb{F}_{2}^{m\times n} , the goal is to pre-process a vector X ∈ 𝔽 2 n X\in\mathbb{F}_{2}^{n} into a data structure of size s s to answer any query ⟨ M i , X ⟩ \left\langle M_{i},X\right\rangle in time t t . We prove that for a random operator M M , any such data structure requires: t ≥ Ω ( min { log ( m / s ) , n / log s } ) . t\geq\Omega(\min\{\log(m/s),n/\log s\}). This result overcomes the well-known logarithmic barrier in static data structures [ MNSW98 , Sie04 , PD06 , PTW08 , Pǎ11 , 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 ⋅ log 1 / d ( n ) ) \Omega(n\cdot\log^{1/d}(n)) for depth- d d circuits with arbitrary gates that compute a specific linear operator M ∈ 𝔽 2 O ( n ) × n 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 m is super-polynomial (e.g., 2 n 1 / 3 2^{n^{1/3}} ), and the total update time is m 0.99 m^{0.99} . Our result for the latter also applies to cases with super-polynomial m m . 1 Introduction A fundamental, long-standing question in the theory of computation is: Can non-linear computation provide an advantage in computing a linear operator? The intuition that non-linear computation offers no significant help has persisted for over 70 years since the seminal work in circuit design by Shannon [ Sha49 ] . For instance, Lupanov [ Lup56 ] and later Valiant [ Val77 , Val92 ] drew on this idea to study the complexity of linear operators. This belief underpins major open problems like matrix rigidity–the search for a linear operator that cannot be computed by small, shallow circuits with linear gates (See the surveys [ Lok09 , Ram20 ] and references therein). Despite its widespread acceptance, this intuition has remained a folklore belief. Only recently did Jukna and Schnitger [ JS11 , Juk12 ] formalize it as an informal conjecture: non-linear gates do not help in computing a linear operator . This conjecture extends naturally to the cell-probe model [ Yao81 ] , the most powerful model of computation for data structures. In this model, we only count memory accesses (probes), while all computation is free. An input is pre-processed into a data structure of s cells (here, we assume 1-bit cells, as we work over \mathbb{F}_{2} ). To answer a query, an algorithm can probe up to t cells and perform arbitrary computation on their contents. Because of its strength, a lower bound in this model applies to any reasonable data structure. This raises an analogous question for data structures: for a cell-probe data structure designed to compute \left\langle M_{i},X\right\rangle for a linear operator M , can non-linear pre-processing of the input X reduce the query time? This can be seen as a cell-probe analogue of the Jukna-Schnitger conjecture (See Section 2 of [ DGW19 ] for detailed discussion). Assuming this intuition is true has led to fruitful research on restricted models where pre-processing is linear or from related classes (See [ Fre81 , Cha90 , Lar14 , Aga17 , DGW19 , AFKL19 , GPRW22 ] and references therein). These models are also deeply connected to matrix rigidity [ DGW19 , NRR20 ] . However, challenging this intuition, there are cases where highly efficient non-linear data structures exist for linear problems with no known linear equivalents [ KU11 ] . Our primary goal is to rigorously establish that for most linear operators, non-linear pre-processing provides no significant advantage . This, in turn, implies an analogous result for circuit complexity. Previous Results Progress on this front has been stalled by technical barriers in the cell-probe model. The primary tool for static cell-probe lower bounds is essentially a counting argument. A seminal result by Miltersen [ Mil93 ] shows that for almost all non-linear problems, if the space s is slightly smaller than the number of possible outputs m (e.g., s=m^{0.99} ), then the query time must be large ( t\geq\Omega(n^{0.99}) ). If we assume linear pre-processing is optimal for linear problems, a similar counting argument yields strong lower bounds. However, this argument breaks down completely when arbitrary non-linear pre-processing is allowed. The number of possible functions to compute even a single pre-processed bit is astronomical ( 2^{2^{n}} ), rendering a simple counting argument over all possible data structures useless. Prior to our work, the best lower bound for an arbitrary linear problem was derived from techniques used for explicit data structure problems [ MNSW98 , Sie04 , PD06 , PTW08 , Pǎ11 ] . These techniques hit a ceiling known as the logarithmic barrier, yielding bounds of the form: t\geq\Omega\left(\frac{\log\frac{|\mathcal{Q}|}{n}}{\log\frac{s}{n}}\right). (1) where |\mathcal{Q}|=m is the number of distinct queries. Breaking this barrier for an explicit data structure is a holy-grail problem, with connections to major open questions in branching programs and circuit complexity [ MNSW98 , DGW19 , Vio18 ] . In summary, it was previously unknown if any linear problem was truly hard against non-linear data structures. For decades, it was not ruled out that highly efficient non-linear data structures (e.g., with t=O(1) and s=|\mathcal{Q}|^{0.1} ) might exist for all linear problems. 1.1 Further Connections 1.1.1 Multiphase Program: Communication versus Cell-Probe A more recent motivation for our work is its connection to the communication version of the Multiphase Conjecture [ Pat10 , Tho13 , Bra22 ] , a problem in 3-player Number-on-Forehead (NOF) communication. Definition 1.1 (Multiphase Communication Game [ Pat10 ] ) . The 3-player Number-On-Forehead (NOF) communication game is defined as follows • The inputs are distributed as follows: Merlin receives the linear operator M\in\{0,1\}^{m\times n} and the vector X\in\{0,1\}^{n} . For a given query index i\in[m] , Alice receives M and i , while Bob receives T and i . • Merlin sends a single-shot message of length m^{0.99} to Bob. • Alice and Bob proceed in standard two-party communication to output \left\langle M_{i},X\right\rangle 1 1 1 Originally, the conjecture was phrased in Merlin sending a message of length o(m) , then Alice and Bob proceeding to output \mathsf{DISJ}(M_{i},X) . However, analogous implications hold from this slightly weaker conjecture for any given i\in[m] . The Multiphase Conjecture (Communication Version) then states that for