Export Citations
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-articleJanuary 2022
Anchored Parallel Repetition for Nonlocal Games
SIAM Journal on Computing (SICOMP), Volume 51, Issue 2Pages 214–253https://doi.org/10.1137/21M1405927We introduce a simple transformation on two-player nonlocal games, called “anchoring,” and prove an exponential-decay parallel repetition theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part ...
- research-articleMay 2009
The detectability lemma and quantum gap amplification
STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computingPages 417–426https://doi.org/10.1145/1536414.1536472The quantum analogue of the constraint satisfaction problem is the fundamental physics question of finding the minimal energy state of a local Hamiltonian --- each term of the Hamiltonian specifies a local constraint whose violation contributes to the ...
- ArticleMay 2006
The PCP theorem by gap amplification
STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of ComputingPages 241–250https://doi.org/10.1145/1132516.1132553We present a new proof of the PCP theorem that is based on a combinatorial amplification lemma. The unsat value of a set of constraints C = (c1,...,cn), denoted UNSAT(C), is the smallest fraction of unsatisfied constraints, ranging over all possible ...