The average sensitivity of bounded-depth formulas

DOI10.1007/S00037-017-0156-0zbMath1396.68050arXiv1508.07677OpenAlexW2733767732MaRDI QIDQ1653335

Benjamin Rossman

Publication date: 3 August 2018

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1508.07677

zbMATH Keywords

lower boundsparity\(\mathrm{AC}^{0}\)

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)

Related Items (4)

Formulas versus Circuits for Small Distance Connectivity ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Unnamed Item ⋮ Criticality of regular formulas

Cites Work

• The average sensitivity of bounded-depth circuits
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Complexity of the realization of a linear function in the class of \(\Pi\)-circuits
• The Quantum Query Complexity of Read-Many Formulas
• Parity, circuits, and the polynomial-time hierarchy
• Formulas vs. circuits for small distance connectivity

This page was built for publication: The average sensitivity of bounded-depth formulas