ECCC-Report TR21-040https://eccc.weizmann.ac.il/report/2021/040Comments and Revisions published for TR21-040en-usMon, 15 Mar 2021 15:23:12 +0200
Paper TR21-040
| Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1 |
Lijie Chen,
Zhenjian Lu,
Xin Lyu,
Igor Carboni Oliveira
https://eccc.weizmann.ac.il/report/2021/040We develop a general framework that characterizes strong average-case lower bounds against circuit classes $\mathcal{C}$ contained in $\mathrm{NC}^1$, such as $\mathrm{AC}^0[\oplus]$ and $\mathrm{ACC}^0$. We apply this framework to show:
- Generic seed reduction: Pseudorandom generators (PRGs) against $\mathcal{C}$ of seed length $\leq n -1$ and error $\varepsilon(n) = n^{-\omega(1)}$ can be converted into PRGs of sub-polynomial seed length.
- Hardness under natural distributions: If $\mathrm{E}$ (deterministic exponential time) is average-case hard against $\mathcal{C}$ under some distribution, then $\mathrm{E}$ is average-case hard against $\mathcal{C}$ under the uniform distribution.
- Equivalence between worst-case and average-case hardness: Worst-case lower bounds against $\mathrm{MAJ} \circ \mathcal{C}$ for problems in $E$ are equivalent to strong average-case lower bounds against $\mathcal{C}$. This can be seen as a certain converse to the Discriminator Lemma [Hajnal et al., JCSS'93].
These results were not known to hold for circuit classes that do not compute majority. Additionally, we prove that classical and recent approaches to worst-case lower bounds against $\mathrm{ACC}^0$ via communication lower bounds for NOF multi-party protocols [Hastad and Goldmann, CC'91; Razborov and Wigderson, IPL'93] and Torus polynomials degree lower bounds [Bhrushundi et al., ITCS'19] also imply strong average-case hardness against $\mathrm{ACC}^0$ under the uniform distribution.
Crucial to these results is the use of non-black-box hardness amplification techniques and the interplay between Majority ($\mathrm{MAJ}$) and Approximate Linear Sum ($\widetilde{\mathrm{SUM}}$) gates. Roughly speaking, while a $\mathrm{MAJ}$ gate outputs $1$ when the sum of the $m$ input bits is at least $m/2$, a $\widetilde{\mathrm{SUM}}$ gate computes a real-valued bounded weighted sum of the input bits and outputs $1$ (resp. $0$) if the sum is close to $1$ (resp. close to $0$), with the promise that one of the two cases always holds. As part of our framework, we explore ideas introduced in [Chen and Ren, STOC'20] to show that, for the purpose of proving lower bounds, a top layer $MAJ$ gate is equivalent to a (weaker) $\widetilde{\mathrm{SUM}}$ gate. Motivated by this result, we extend the algorithmic method and establish stronger lower bounds against bounded-depth circuits with layers of $\mathrm{MAJ}$ and $\widetilde{\mathrm{SUM}}$ gates. Among them, we prove that:
- Lower bound: $\mathrm{NQP}$ does not admit fixed quasi-polynomial size $\mathrm{MAJ} \circ \widetilde{\mathrm{SUM}} \circ \mathrm{ACC}^0 \circ \mathrm{THR}$ circuits.
This is the first explicit lower bound against circuits with distinct layers of $\mathrm{MAJ}$, $\widetilde{\mathrm{SUM}}$, and $\mathrm{THR}$ gates. Consequently, if the aforementioned equivalence between $\mathrm{MAJ}$ and $\widetilde{\mathrm{SUM}}$ as a top gate can be extended to intermediate layers, long sought-after lower bounds against the class $\mathrm{THR} \circ \mathrm{THR}$ of depth-$2$ polynomial-size threshold circuits would follow.Mon, 15 Mar 2021 15:23:12 +0200https://eccc.weizmann.ac.il/report/2021/040