Circuit Lower Bounds for Merlin–Arthur Classes

DOI10.1137/070702680zbMath1192.68302OpenAlexW1989076199MaRDI QIDQ3575158

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

derandomizationcomplexity theorycircuit lower boundsaverage-case lower boundsMerlin-Arthur classesclasses with advice

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (17)

Circuit lower bounds from learning-theoretic approaches ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ The power of natural properties as oracles ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Unnamed Item ⋮ Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma ⋮ Unnamed Item ⋮ On Pseudodeterministic Approximation Algorithms. ⋮ On fixed-polynomial size circuit lower bounds for uniform polynomials in the sense of Valiant ⋮ Unions of Disjoint NP-Complete Sets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Relations and equivalences between circuit lower bounds and karp-lipton theorems ⋮ Hardness magnification near state-of-the-art lower bounds ⋮ 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

This page was built for publication: Circuit Lower Bounds for Merlin–Arthur Classes