Circuit Lower Bounds for Average-Case MA

DOI10.1007/978-3-319-20297-6_18zbMath1466.68039OpenAlexW1174733130WikidataQ57838078 ScholiaQ57838078MaRDI QIDQ3194723

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

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) 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 (1)

How much randomness is needed to convert MA protocols to AM protocols?

Cites Work

• A Boolean function requiring 3n network size
• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Pseudorandomness and average-case complexity via uniform reductions
• On Fast Heuristic Non-deterministic Algorithms and Short Heuristic Proofs
• Algebrization
• Circuit-size lower bounds and non-reducibility to sparse sets
• Structural Complexity of AvgBPP
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Circuit Lower Bounds for Average-Case MA