1 citations · 1 across the 3 of their papers we have counts for
3 papers
quant-ph2024★ 1 cited
The status of the quantum PCP conjecture (games version)
Anand Natarajan, Chinmay Nirkhe
In classical complexity theory, the two definitions of probabilistically checkable proofs -- the constraint satisfaction and the nonlocal games version -- are computationally equal…
quant-ph2023
Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification
Anand Natarajan, Tina Zhang
We present a step towards the goal of producing a general cryptographic 'compilation' procedure which can translate any entangled nonlocal game into a single-prover interactive pro…
quant-ph2023
Quantum free games
Anand Natarajan, Tina Zhang
The complexity of free games with two or more classical players was essentially settled by Aaronson, Impagliazzo, and Moshkovitz (CCC'14). There are two complexity classes that can…