Anand Natarajan

According to our database, Anand Natarajan authored at least 26 papers between 2015 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

A distribution testing oracle separation between QMA and QCMA.

Anand Natarajan, Chinmay Nirkhe

Quantum, 2024

Quantum Locally Testable Code with Constant Soundness.

Andrew W. Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu

Quantum, 2024

Classical Commitments to Quantum States.

Sam Gunn, Yael Tauman Kalai, Anand Natarajan, Agi Villanyi

IACR Cryptol. ePrint Arch., 2024

A Computational Tsirelson's Theorem for the Value of Compiled XOR Games.

David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang

IACR Cryptol. ePrint Arch., 2024

The status of the quantum PCP conjecture (games version).

Anand Natarajan, Chinmay Nirkhe

CoRR, 2024

Succinct Arguments for QMA from Standard Assumptions via Compiled Nonlocal Games.

Tony Metger, Anand Natarajan, Tina Zhang

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise.

Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao

Proceedings of the 39th Computational Complexity Conference, 2024

2023

A Collapsible Polynomial Hierarchy for Promise Problems.

Chirag Falor, Shu Ge, Anand Natarajan

CoRR, 2023

Quantum Free Games.

Anand Natarajan, Tina Zhang

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification.

Anand Natarajan, Tina Zhang

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

A Distribution Testing Oracle Separating QMA and QCMA.

Anand Natarajan, Chinmay Nirkhe

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Quantum Locally Testable Code with Exotic Parameters.

Andrew W. Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu

CoRR, 2022

Quantum Search-To-Decision Reductions and the State Synthesis Problem.

Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen

Proceedings of the 37th Computational Complexity Conference, 2022

2021

MIP* = RE.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

Commun. ACM, 2021

Quantum soundness of testing tensor codes.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Quantum soundness of the classical low individual degree test.

Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen

CoRR, 2020

2019

NEEXP in MIP.

Anand Natarajan, John Wright

CoRR, 2019

Algorithms, Bounds, and Strategies for Entangled XOR Games.

Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

NEEXP is Contained in MIP.

Anand Natarajan, John Wright

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA.

Anand Natarajan, Thomas Vidick

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Two-Player Entangled Games are NP-Hard.

Anand Natarajan, Thomas Vidick

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

A quantum linearity test for robustly verifying entanglement.

Anand Natarajan, Thomas Vidick

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Robust self-testing of many-qubit states.

Anand Natarajan, Thomas Vidick

CoRR, 2016

Limitations of semidefinite programs for separable states and entangled games.

Aram W. Harrow, Anand Natarajan, Xiaodi Wu

CoRR, 2016

Tight SoS-Degree Bounds for Approximate Nash Equilibria.

Aram W. Harrow, Anand Natarajan, Xiaodi Wu

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

An improved semidefinite programming hierarchy for testing entanglement.

Aram W. Harrow, Anand Natarajan, Xiaodi Wu

CoRR, 2015