Circuit lower bounds for Merlin-Arthur classes

DOI10.1137/070702680MaRDI QIDQ3575158zbMATH OpenOpenAlexFDO

Authors Rahul Santhanam

Publication date 7 July 2010

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/070702680

zbMATH Keywords

average-case lower boundscircuit lower boundsclasses with advicecomplexity theoryderandomizationMerlin-Arthur classes

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) 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 average-case MA
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• If NP has polynomial-size circuits, then MA=AM

Cited in

(28)

• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Nondeterministic circuit lower bounds from mildly derandomizing Arthur-Merlin games
• Proving that \(\mathrm{prBPP}=\mathrm{prP}\) is as hard as proving that ``almost NP is not contained in P/poly
• On the probabilistic closure of the loose unambiguous hierarchy
• On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant
• Circuit lower bounds from learning-theoretic approaches
• Circuit lower bounds for average-case MA
• Circuit lower bounds for Merlin-Arthur classes
• Finding irrefutable certificates for \({\mathrm{S}_2}^p\) via Arthur and Merlin
• On Pseudodeterministic Approximation Algorithms.
• Hardness magnification near state-of-the-art lower bounds
• Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization
• Hardness magnification near state-of-the-art lower bounds
• Relations and equivalences between circuit lower bounds and karp-lipton theorems
• scientific article; zbMATH DE number 7250146 (Why is no real title available?)
• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
• Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
• Unions of disjoint NP-complete sets
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• The power of natural properties as oracles
• Improving \(3N\) circuit complexity lower bounds
• Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
• If NP has polynomial-size circuits, then MA=AM
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
• On exponential-time hypotheses, derandomization, and circuit lower bounds
• Symmetric exponential time requires near-maximum circuit size
• Oblivious complexity classes revisited: lower bounds and hierarchies

This page was built for publication: Circuit lower bounds for Merlin-Arthur classes

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