Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Anand Natarajan and Chinmay Nirkhe. A Distribution Testing Oracle Separating QMA and QCMA. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 22:1-22:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{natarajan_et_al:LIPIcs.CCC.2023.22, author = {Natarajan, Anand and Nirkhe, Chinmay}, title = {{A Distribution Testing Oracle Separating QMA and QCMA}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {22:1--22:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.22}, URN = {urn:nbn:de:0030-drops-182928}, doi = {10.4230/LIPIcs.CCC.2023.22}, annote = {Keywords: quantum non-determinism, complexity theory} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen. Quantum Search-To-Decision Reductions and the State Synthesis Problem. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 5:1-5:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{irani_et_al:LIPIcs.CCC.2022.5, author = {Irani, Sandy and Natarajan, Anand and Nirkhe, Chinmay and Rao, Sujit and Yuen, Henry}, title = {{Quantum Search-To-Decision Reductions and the State Synthesis Problem}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {5:1--5:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.5}, URN = {urn:nbn:de:0030-drops-165674}, doi = {10.4230/LIPIcs.CCC.2022.5}, annote = {Keywords: Search-to-decision, state synthesis, quantum computing} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Tony Metger and Thomas Vidick. Self-Testing of a Single Quantum Device Under Computational Assumptions. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 19:1-19:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{metger_et_al:LIPIcs.ITCS.2021.19, author = {Metger, Tony and Vidick, Thomas}, title = {{Self-Testing of a Single Quantum Device Under Computational Assumptions}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {19:1--19:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.19}, URN = {urn:nbn:de:0030-drops-135581}, doi = {10.4230/LIPIcs.ITCS.2021.19}, annote = {Keywords: Quantum computing, quantum cryptography, device-independence, self-testing, post-quantum cryptography} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Srijita Kundu, Jamie Sikora, and Ernest Y.-Z. Tan. A Device-Independent Protocol for XOR Oblivious Transfer. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 12:1-12:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{kundu_et_al:LIPIcs.TQC.2020.12, author = {Kundu, Srijita and Sikora, Jamie and Tan, Ernest Y.-Z.}, title = {{A Device-Independent Protocol for XOR Oblivious Transfer}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {12:1--12:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-146-7}, ISSN = {1868-8969}, year = {2020}, volume = {158}, editor = {Flammia, Steven T.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.12}, URN = {urn:nbn:de:0030-drops-127579}, doi = {10.4230/LIPIcs.TQC.2020.12}, annote = {Keywords: Quantum cryptography, device independence, oblivious transfer, semidefinite programming, security analysis} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Matthew Coudron and William Slofstra. Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 25:1-25:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{coudron_et_al:LIPIcs.CCC.2019.25, author = {Coudron, Matthew and Slofstra, William}, title = {{Complexity Lower Bounds for Computing the Approximately-Commuting Operator Value of Non-Local Games to High Precision}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {25:1--25:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.25}, URN = {urn:nbn:de:0030-drops-108478}, doi = {10.4230/LIPIcs.CCC.2019.25}, annote = {Keywords: Quantum complexity theory, Non-local game, Multi-prover interactive proof, Entanglement} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, and Anand Natarajan. Algorithms, Bounds, and Strategies for Entangled XOR Games. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 10:1-10:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{benewatts_et_al:LIPIcs.ITCS.2019.10, author = {Bene Watts, Adam and Harrow, Aram W. and Kanwar, Gurtej and Natarajan, Anand}, title = {{Algorithms, Bounds, and Strategies for Entangled XOR Games}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.10}, URN = {urn:nbn:de:0030-drops-101032}, doi = {10.4230/LIPIcs.ITCS.2019.10}, annote = {Keywords: Nonlocal games, XOR Games, Pseudotelepathy games, Multipartite entanglement} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Anand Natarajan and Thomas Vidick. Retracted: Two-Player Entangled Games are NP-Hard. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{natarajan_et_al:LIPIcs.CCC.2018.20, author = {Natarajan, Anand and Vidick, Thomas}, title = {{Retracted: Two-Player Entangled Games are NP-Hard}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {20:1--20:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.20}, URN = {urn:nbn:de:0030-drops-88696}, doi = {10.4230/LIPIcs.CCC.2018.20}, annote = {Keywords: low-degree testing, entangled nonlocal games, multi-prover interactive proof systems} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Aram Harrow, Anand V. Natarajan, and Xiaodi Wu. Tight SoS-Degree Bounds for Approximate Nash Equilibria. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 22:1-22:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{harrow_et_al:LIPIcs.CCC.2016.22, author = {Harrow, Aram and Natarajan, Anand V. and Wu, Xiaodi}, title = {{Tight SoS-Degree Bounds for Approximate Nash Equilibria}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {22:1--22:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.22}, URN = {urn:nbn:de:0030-drops-58565}, doi = {10.4230/LIPIcs.CCC.2016.22}, annote = {Keywords: Approximate Nash Equilibrium, Sum of Squares, LP, SDP} }
Feedback for Dagstuhl Publishing