An average-case lower bound against \(\mathsf{ACC}^0\)

DOI10.1007/978-3-319-77404-6_24zbMath1485.68102OpenAlexW2794128811MaRDI QIDQ2294696

Ruiwen Chen, Rahul Santhanam, Igor C. Oliveira

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 complexitypseudorandomnesscircuit lower boundslearning and natural properties

Mathematics Subject Classification ID

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

Related Items (6)

Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms ⋮ Depth-\(d\) threshold circuits vs. depth-\((d+1)\) and-or trees ⋮ Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms ⋮ Average-case rigidity lower bounds ⋮ Upper bound for torus polynomials

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