Circuit lower bounds for average-case MA

DOI10.1007/978-3-319-20297-6_18MaRDI QIDQ3194723zbMATH OpenOpenAlexWikidataFDO

Authors Alexander Knop

Publication date 20 October 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Merlin-Arthur classes

Mathematics Subject Classification ID

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

Recommendations

• Circuit lower bounds for Merlin-Arthur classes
• Circuit lower bounds for Merlin-Arthur classes
• An average-case lower bound against \(\mathsf{ACC}^0\)
• An average-case depth hierarchy theorem for Boolean circuits
• Some Results on Average-Case Hardness Within the Polynomial Hierarchy

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• A Boolean function requiring 3n network size
• Algebrization: a new barrier in complexity theory
• Circuit lower bounds for Merlin-Arthur classes
• Circuit-size lower bounds and non-reducibility to sparse sets
• scientific article; zbMATH DE number 5081744 (Why is no real title available?)
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 1335875 (Why is no real title available?)
• scientific article; zbMATH DE number 2019635 (Why is no real title available?)
• On fast heuristic non-deterministic algorithms and short heuristic proofs
• Pseudorandomness and average-case complexity via uniform reductions
• Structural Complexity of AvgBPP

Cited in

(3)

• How much randomness is needed to convert MA protocols to AM protocols?
• Circuit lower bounds for Merlin-Arthur classes
• Circuit lower bounds for Merlin-Arthur classes

This page was built for publication: Circuit lower bounds for average-case MA

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