Two combinatorial MA-complete problems

DOI10.4230/LIPICS.ITCS.2021.36MaRDI QIDQ7229322zbMATH OpenFDO

Authors Dorit Aharonov, Alex Bredariol Grilo

Publication date 15 April 2026

Copyright license Creative Commons Attribution 3.0 Unported

Full work available at URL https://doi.org/10.4230/LIPICS.ITCS.2021.36

zbMATH Keywords

random walksMerlin-Arthur proof systemsconstraint sastifation problem

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 4057011 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 1776257 (Why is no real title available?)
• A PCP characterization of AM
• A Pseudorandom Generator from any One-way Function
• Adiabatic quantum computation is equivalent to standard quantum computation
• Another Proof That $\mathcal{BPP}\subseteq \mathcal{PH}$ (and More)
• Complexity of stoquastic frustration-free Hamiltonians
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Hardness vs randomness
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Pseudorandom generators without the XOR lemma
• The PCP theorem by gap amplification
• BPP has subexponential time simulations unless EXPTIME has publishable proofs

This page was built for publication: Two combinatorial MA-complete problems

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