An average-case lower bound against ACC^0

DOI10.1007/978-3-319-77404-6_24MaRDI QIDQ2294696zbMATH OpenOpenAlexFDO

Authors Ruiwen Chen, Igor C. Oliveira, Rahul Santhanam

Publication date 12 February 2020

Full work available at URL https://doi.org/10.1007/978-3-319-77404-6_24

zbMATH Keywords

average-case complexitycircuit lower boundslearning and natural propertiespseudorandomness

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Nonuniform ACC circuit lower bounds
• On limited nondeterminism and ACC circuit lower bounds
• NEXP does not have non-uniform quasipolynomial-size ACC circuits of o( n) depth
• Average-case lower bounds and satisfiability algorithms for small threshold circuits
• Average-case lower bounds and satisfiability algorithms for small threshold circuits

Cited in

(11)

• Average-case rigidity lower bounds
• Upper bound for torus polynomials
• Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms
• On limited nondeterminism and ACC circuit lower bounds
• NEXP does not have non-uniform quasipolynomial-size ACC circuits of o( n) depth
• Circuit lower bounds for average-case MA
• Average-case lower bounds for the plurality problem
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits

This page was built for publication: An average-case lower bound against \(\mathsf{ACC}^0\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294696)