ECCC-Report TR20-193https://eccc.weizmann.ac.il/report/2020/193Comments and Revisions published for TR20-193en-usTue, 29 Dec 2020 18:17:22 +0200
Paper TR20-193
| Average-case rigidity lower bounds |
Xuangui Huang,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/193It is shown that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\P_{x,y}[f(x,y)\ne M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, where $k \leq \Theta(\sqrt{n})$ and $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently small $\delta > 0$.
This generalizes recent results which bound below the probability by $1/2-\Omega(1)$ or apply to constant-depth circuits.
The result is a step towards obtaining data-structure lower bounds for E$^\mathbf{NP}$: they would follow from a better trade-off between the probability bound and $\rho$.
Tue, 29 Dec 2020 18:17:22 +0200https://eccc.weizmann.ac.il/report/2020/193