标题： 线性算子的下界 显示英文标题

标题： Lower Bounds for Linear Operators

摘要： 我们考虑在单元探测模型下计算线性算子的静态数据结构问题。 给定一个线性算子$M \in \mathbb{F}_2^{m \times n}$，目标是将向量$X \in \mathbb{F}_2^n$预处理成一个大小为$s$的数据结构，以时间$t$回答任何查询$\langle M_i , X \rangle$。 我们证明，对于一个随机算子$M$，任何这样的数据结构都需要： $$ t \geq \Omega ( \min \{ \log (m/s) , n / \log s \} ).$$这一结果通过使用随机线性算子克服了静态数据结构中著名的对数障碍 [MNSW98, Sie04, PD06, PTW08, Pat11, DGW19]。 此外，它为确认一个几十年来的常识性猜想提供了首次重大进展：即非线性预处理在计算大多数线性算子时不会带来显著帮助。 我们证明的直接修改也得出一个线缆下界$\Omega(n \cdot \log^{1/d}(n))$，对于计算特定线性算子$M \in \mathbb{F}_2^{O(n) \times n}$的深度$d$电路，即使在某些小常数优势超过随机猜测的情况下也成立。 此界限甚至适用于仅比随机猜测有小常数优势的电路，优于[RS03, Che08a, Che08b, GHK+13]对随机算子的长期结果。 最后，我们的工作部分解决了Multiphase猜想 [Pat10] 的通信形式，并推进了Jukna-Schnitger猜想 [JS11, Juk12]。 我们通过考虑当查询次数$m$超多项式（例如$2^{n^{1/3}}$）时的内积（模2）问题（而不是集合不相交问题），以及总更新时间是$m^{0.99}$来解决前者。 我们对后者的结果也适用于超多项式$m$的情况。 显示英文摘要

摘要： 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 \Omega ( \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 $\Omega(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$.