Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Dorit Aharonov:

TR20-043 | 29th March 2020
Dorit Aharonov, Alex Bredariol Grilo

A combinatorial MA-complete problem

Revisions: 2

Despite the interest in the complexity class MA, the randomized analog of NP, there is just a couple of known natural (promise-)MA-complete problems, the first due to Bravyi and Terhal (SIAM Journal of Computing 2009) and the second due to Bravyi (Quantum Information and Computation 2015). Surprisingly, both problems are ... more >>>

TR19-010 | 21st January 2019
Dorit Aharonov, Alex Bredariol Grilo

Stoquastic PCP vs. Randomness

The derandomization of MA, the probabilistic version of NP, is a long standing open question. In this work, we connect this problem to a variant of another major problem: the quantum PCP conjecture. Our connection goes through the surprising quantum characterization of MA by Bravyi and Terhal. They proved the ... more >>>

ISSN 1433-8092 | Imprint