期刊
出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3313276.3316348
关键词
circuit lower bound; codes; data structures; rigidity
资金
- NSF [DMS-1451191, CCF-1523816, CCF-1844887]
- Rabin Postdoctoral Fellowship
We show that static data structure lower bounds in the group (linear) model imply semi-explicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of t >= omega(log(2) n) on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space (s = (1 + epsilon)n), would already imply a semi-explicit (P-NP) construction of rigid matrices with significantly better parameters than the current state of art (Alon, Panigrahy and Yekhanin, 2009). Our results further assert that polynomial (t >= n(delta)) data structure lower bounds against near-optimal space, would imply super-linear circuit lower bounds for log-depth linear circuits (a four-decade open question). In the succinct space regime (s = n + o(n)), we show that any improvement on current cell-probe lower bounds in the linear model would also imply new rigidity bounds. Our results rely on a new connection between the inner and outer dimensions of a matrix (Paturi and Pudlak, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据