Anand Natarajan

38 papers A* 8A 7Journal 23

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	A Computational Tsirelson's Theorem for the Value of Compiled XOR Games. Quantum David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang
2026	A	`conf`	Two Bases Suffice for QMA ₁-Completeness. ITCS Henry Ma, Anand Natarajan
2025	A*	`conf`	Classical Commitments to Quantum States. STOC Sam Gunn, Yael Tauman Kalai, Anand Natarajan, Ági Villányi
2025	J	`jnl`	The Computational Advantage of MIP* Vanishes in the Presence of Noise. J. ACM Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao
2025	J	`jnl`	Two bases suffice for QMA1-completeness. CoRR Henry Ma, Anand Natarajan
2024	J	`jnl`	A Computational Tsirelson's Theorem for the Value of Compiled XOR Games. IACR Cryptol. ePrint Arch. David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang
2024	J	`jnl`	A distribution testing oracle separation between QMA and QCMA. Quantum Anand Natarajan, Chinmay Nirkhe
2024	J	`jnl`	Classical Commitments to Quantum States. IACR Cryptol. ePrint Arch. Sam Gunn, Yael Tauman Kalai, Anand Natarajan, Agi Villanyi
2024	J	`jnl`	Quantum Locally Testable Code with Constant Soundness. Quantum Andrew W. Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu
2024	A*	`conf`	Succinct Arguments for QMA from Standard Assumptions via Compiled Nonlocal Games. FOCS Tony Metger, Anand Natarajan, Tina Zhang
2024	J	`jnl`	Succinct arguments for QMA from standard assumptions via compiled nonlocal games. CoRR Tony Metger, Anand Natarajan, Tina Zhang
2024	A	`conf`	The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise. CCC Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao
2024	J	`jnl`	The status of the quantum PCP conjecture (games version). CoRR Anand Natarajan, Chinmay Nirkhe
2023	J	`jnl`	A Collapsible Polynomial Hierarchy for Promise Problems. CoRR Chirag Falor, Shu Ge, Anand Natarajan
2023	A	`conf`	A Distribution Testing Oracle Separating QMA and QCMA. CCC Anand Natarajan, Chinmay Nirkhe
2023	A*	`conf`	Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification. FOCS Anand Natarajan, Tina Zhang
2023	A*	`conf`	Quantum Free Games. STOC Anand Natarajan, Tina Zhang
2023	J	`jnl`	Quantum free games. CoRR Anand Natarajan, Tina Zhang
2023	J	`jnl`	The Computational Advantage of MIP* Vanishes in the Presence of Noise. CoRR Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao
2022	J	`jnl`	Quantum Locally Testable Code with Exotic Parameters. CoRR Andrew W. Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu
2022	A	`conf`	Quantum Search-To-Decision Reductions and the State Synthesis Problem. CCC Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen
2021	J	`jnl`	MIP* = RE. Commun. ACM Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2021	J	`jnl`	Quantum search-to-decision reductions and the state synthesis problem. CoRR Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen
2021	A*	`conf`	Quantum soundness of testing tensor codes. FOCS Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2021	J	`jnl`	Quantum soundness of testing tensor codes. CoRR Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2020	J	`jnl`	MIP*=RE. CoRR Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2020	J	`jnl`	Quantum soundness of the classical low individual degree test. CoRR Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
2019	A	`conf`	Algorithms, Bounds, and Strategies for Entangled XOR Games. ITCS Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan
2019	J	`jnl`	NEEXP in MIP. CoRR Anand Natarajan, John Wright
2019	A*	`conf`	NEEXP is Contained in MIP. FOCS Anand Natarajan, John Wright
2018	J	`jnl`	Algorithms, Bounds, and Strategies for Entangled XOR Games. CoRR Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan
2018	A*	`conf`	Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. FOCS Anand Natarajan, Thomas Vidick
2018	A	`conf`	Two-Player Entangled Games are NP-Hard. CCC Anand Natarajan, Thomas Vidick
2017	A*	`conf`	A quantum linearity test for robustly verifying entanglement. STOC Anand Natarajan, Thomas Vidick
2016	J	`jnl`	Limitations of semidefinite programs for separable states and entangled games. CoRR Aram W. Harrow, Anand Natarajan, Xiaodi Wu
2016	J	`jnl`	Robust self-testing of many-qubit states. CoRR Anand Natarajan, Thomas Vidick
2016	A	`conf`	Tight SoS-Degree Bounds for Approximate Nash Equilibria. CCC Aram W. Harrow, Anand Natarajan, Xiaodi Wu
2015	J	`jnl`	An improved semidefinite programming hierarchy for testing entanglement. CoRR Aram W. Harrow, Anand Natarajan, Xiaodi Wu