Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-193 | 29th December 2020 18:17

#### Average-case rigidity lower bounds

TR20-193
Authors: Xuangui Huang, Emanuele Viola
Publication: 29th December 2020 18:17
Downloads: 140
Keywords:

Abstract:

It 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$.

ISSN 1433-8092 | Imprint