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

DOI10.1007/978-3-031-09574-0_21OpenAlexW4285197414MaRDI QIDQ2097236

Nikolai K. Vereshchagin

Publication date: 11 November 2022

Full work available at URL: https://doi.org/10.1007/978-3-031-09574-0_21

zbMATH Keywords

derandomizationMerlin-Arthur protocoloraclesArthur-Merlin protocol

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• BPP and the polynomial hierarchy
• Does co-NP have short interactive proofs ?
• Derandomized graph products
• Algebrization
• Circuit Lower Bounds for Average-Case MA
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

This page was built for publication: How much randomness is needed to convert MA protocols to AM protocols?