Anand Natarajan

Publication Activity (10 Years)

Years Active: 2004-2024
Publications (10 Years): 31

Top Topics

Nash Equilibria

Quantum Computing

Top Venues

Publications

Anand Natarajan, Chinmay Nirkhe
The status of the quantum PCP conjecture (games version). CoRR (2024)
Tony Metger, Anand Natarajan, Tina Zhang
Succinct arguments for QMA from standard assumptions via compiled nonlocal games. CoRR (2024)
Sam Gunn, Yael Tauman Kalai, Anand Natarajan, Agi Villanyi
Classical Commitments to Quantum States. IACR Cryptol. ePrint Arch. 2024 (2024)
Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao
The Computational Advantage of MIP^∗ Vanishes in the Presence of Noise. CCC (2024)
David Cui, Giulio Malavolta, Arthur Mehta, Anand Natarajan, Connor Paddock, Simon Schmidt, Michael Walter, Tina Zhang
A Computational Tsirelson's Theorem for the Value of Compiled XOR Games. IACR Cryptol. ePrint Arch. 2024 (2024)
Mark Zhao, Satadru Pan, Niket Agarwal, Zhaoduo Wen, David Xu, Anand Natarajan, Pavan Kumar, Shiva Shankar P., Ritesh Tijoriwala, Karan Asher, Hao Wu, Aarti Basant, Daniel Ford, Delia David, Nezih Yigitbasi, Pratap Singh, Carole-Jean Wu
Tectonic-Shift: A Composite Storage Fabric for Large-Scale ML Training. USENIX Annual Technical Conference (2023)
Anand Natarajan, Tina Zhang
Bounding the Quantum Value of Compiled Nonlocal Games: From CHSH to BQP Verification. FOCS (2023)
Anand Natarajan, Tina Zhang
Quantum Free Games. STOC (2023)
Anand Natarajan, Tina Zhang
Quantum free games. CoRR (2023)
Anand Natarajan, Chinmay Nirkhe
A Distribution Testing Oracle Separating QMA and QCMA. CCC (2023)
Yangjing Dong, Honghao Fu, Anand Natarajan, Minglong Qin, Haochen Xu, Penghui Yao
The Computational Advantage of MIP* Vanishes in the Presence of Noise. CoRR (2023)
Chirag Falor, Shu Ge, Anand Natarajan
A Collapsible Polynomial Hierarchy for Promise Problems. CoRR (2023)
Andrew Cross, Zhiyang He, Anand Natarajan, Mario Szegedy, Guanyu Zhu
Quantum Locally Testable Code with Exotic Parameters. CoRR (2022)
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen
Quantum Search-To-Decision Reductions and the State Synthesis Problem. CCC (2022)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. FOCS (2022)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
MIP* = RE. Commun. ACM 64 (11) (2021)
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, Henry Yuen
Quantum search-to-decision reductions and the state synthesis problem. CoRR (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. CoRR (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of testing tensor codes. FOCS (2021)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
MIP*=RE. CoRR (2020)
Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, Henry Yuen
Quantum soundness of the classical low individual degree test. CoRR (2020)
Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan
Algorithms, Bounds, and Strategies for Entangled XOR Games. ITCS (2019)
Anand Natarajan, John Wright
NEEXP in MIP. CoRR (2019)
Anand Natarajan, John Wright
NEEXP is Contained in MIP. FOCS (2019)
Anand Natarajan, Thomas Vidick
Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA. FOCS (2018)
Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan
Algorithms, Bounds, and Strategies for Entangled XOR Games. CoRR (2018)
Anand Natarajan, Thomas Vidick
Two-Player Entangled Games are NP-Hard. Computational Complexity Conference (2018)
Anand Natarajan, Thomas Vidick
A quantum linearity test for robustly verifying entanglement. STOC (2017)
Aram W. Harrow, Anand Natarajan, Xiaodi Wu
Tight SoS-Degree Bounds for Approximate Nash Equilibria. Computational Complexity Conference (2016)
Anand Natarajan, Thomas Vidick
Robust self-testing of many-qubit states. CoRR (2016)
Aram W. Harrow, Anand Natarajan, Xiaodi Wu
Limitations of semidefinite programs for separable states and entangled games. CoRR (2016)
Aram W. Harrow, Anand Natarajan, Xiaodi Wu
An improved semidefinite programming hierarchy for testing entanglement. CoRR (2015)
Anand Natarajan, Thomas Vidick
Constant-Soundness Interactive Proofs for Local Hamiltonians. CoRR (2015)
Murali Venkatesh, Anand Natarajan
Institutional Work and Artifact Evolution. ICIS (2011)
Anand Natarajan, Liaquat Hossain
Towards a Social Network Approach for Monitoring Insider Threats to Information Security. ISI (2004)