Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > DORIT AHARONOV:
All reports by Author Dorit Aharonov:

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