License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2021.51
URN: urn:nbn:de:0030-drops-141202
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14120/
Chen, Lijie ;
Lu, Zhenjian ;
Lyu, Xin ;
Oliveira, Igor C.
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹
Abstract
We develop a general framework that characterizes strong average-case lower bounds against circuit classes ? contained in NC¹, such as AC⁰[⊕] and ACC⁰. We apply this framework to show:
- Generic seed reduction: Pseudorandom generators (PRGs) against ? of seed length ≤ n -1 and error ε(n) = n^{-ω(1)} can be converted into PRGs of sub-polynomial seed length.
- Hardness under natural distributions: If ? (deterministic exponential time) is average-case hard against ? under some distribution, then ? is average-case hard against ? under the uniform distribution.
- Equivalence between worst-case and average-case hardness: Worst-case lower bounds against MAJ∘? for problems in ? are equivalent to strong average-case lower bounds against ?. 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 ACC⁰ via communication lower bounds for NOF multi-party protocols [Håstad 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 ACC⁰ under the uniform distribution.
Crucial to these results is the use of non-black-box hardness amplification techniques and the interplay between Majority (MAJ) and Approximate Linear Sum (SUM̃) gates. Roughly speaking, while a MAJ gate outputs 1 when the sum of the m input bits is at least m/2, a 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) SUM̃ gate. Motivated by this result, we extend the algorithmic method and establish stronger lower bounds against bounded-depth circuits with layers of MAJ and SUM̃ gates. Among them, we prove that:
- Lower bound: NQP does not admit fixed quasi-polynomial size MAJ∘SUM̃∘ACC⁰∘THR circuits.
This is the first explicit lower bound against circuits with distinct layers of MAJ, SUM̃, and THR gates. Consequently, if the aforementioned equivalence between MAJ and SUM̃ as a top gate can be extended to intermediate layers, long sought-after lower bounds against the class THR∘THR of depth-2 polynomial-size threshold circuits would follow.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs.ICALP.2021.51,
author = {Chen, Lijie and Lu, Zhenjian and Lyu, Xin and Oliveira, Igor C.},
title = {{Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {51:1--51:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-195-5},
ISSN = {1868-8969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14120},
URN = {urn:nbn:de:0030-drops-141202},
doi = {10.4230/LIPIcs.ICALP.2021.51},
annote = {Keywords: circuit complexity, average-case hardness, complexity lower bounds}
}
|
Keywords: |
|
circuit complexity, average-case hardness, complexity lower bounds |
|
Collection: |
|
48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
02.07.2021 |
