Abstract
We develop a general framework that characterizes strong averagecase 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 subpolynomial seed length.
 Hardness under natural distributions: If 𝖤 (deterministic exponential time) is averagecase hard against 𝒞 under some distribution, then 𝖤 is averagecase hard against 𝒞 under the uniform distribution.
 Equivalence between worstcase and averagecase hardness: Worstcase lower bounds against MAJ∘𝒞 for problems in 𝖤 are equivalent to strong averagecase 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 worstcase lower bounds against ACC⁰ via communication lower bounds for NOF multiparty 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 averagecase hardness against ACC⁰ under the uniform distribution.
Crucial to these results is the use of nonblackbox 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 realvalued 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 boundeddepth circuits with layers of MAJ and SUM̃ gates. Among them, we prove that:
 Lower bound: NQP does not admit fixed quasipolynomial 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 soughtafter lower bounds against the class THR∘THR of depth2 polynomialsize 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 AverageCase Complexity Below NC¹}},
booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
pages = {51:151:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771955},
ISSN = {18688969},
year = {2021},
volume = {198},
editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14120},
URN = {urn:nbn:de:0030drops141202},
doi = {10.4230/LIPIcs.ICALP.2021.51},
annote = {Keywords: circuit complexity, averagecase hardness, complexity lower bounds}
}
Keywords: 

circuit complexity, averagecase hardness, complexity lower bounds 
Collection: 

48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) 
Issue Date: 

2021 
Date of publication: 

02.07.2021 