Rudolph, Dorian, et al. “Quantum 2-SAT on Low Dimensional Systems Is $\'6dathsfQMA_1$-Complete:  Direct Embeddings and Black-Box Simulation.” ArXiv:2401.02368, 2024.
LibreCat: /record/50272
arXiv: 2401.02368

Gharibian, Sevag. “Guest Column: The 7 Faces of Quantum NP.” ACM SIGACT News, vol. 54, no. 4, 2024, pp. 54–91.
LibreCat: /record/48544

Agarwal, Avantika, et al. “Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower  Bounds.” ArXiv:2401.01633, 2024.
LibreCat: /record/50273
arXiv: 2401.01633

Gharibian, Sevag, and Jonas Kamminga. “BQP, Meet NP: Search-to-Decision Reductions and Approximate Counting.” Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP).
LibreCat: /record/50406
arXiv: 2401.03943

Gharibian, Sevag, and Dorian Rudolph. “Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover  Interactive Proofs into Unentanglement.”10.4230/LIPIcs.ITCS.2023.53__14th Innovations in Theoretical Computer Science (ITCS), vol. 251, 2023, p. 53:1-53:23, doi:10.4230/LIPIcs.ITCS.2023.53.
LibreCat: /record/31872
DOI: 10.4230/LIPIcs.ITCS.2023.53
arXiv: 2206.05243

Gharibian, Sevag, et al. “The Complexity of Translationally Invariant Problems beyond Ground State Energies.”https://doi.org/10.4230/LIPIcs.STACS.2023.54__Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), vol. 254, 2023, p. 54:1-54:21, doi:https://doi.org/10.4230/LIPIcs.STACS.2023.54.
LibreCat: /record/20841
DOI: https://doi.org/10.4230/LIPIcs.STACS.2023.54
arXiv: 2012.12717

Bittel, Lennart, et al. “The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate.”10.4230/LIPIcs.CCC.2023.34__Proceedings of the 38th Computational Complexity Conference (CCC), vol. 264, no. 34, 2023, p. 34:1-34:24, doi:10.4230/LIPIcs.CCC.2023.34.
LibreCat: /record/34138
DOI: 10.4230/LIPIcs.CCC.2023.34
arXiv: 2211.12519

Gharibian, Sevag, et al. “Improved Hardness Results for the Guided Local Hamiltonian Problem.”10.4230/LIPIcs.ICALP.2023.32__Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), vol. 261, no. 32, 2023, pp. 1–19, doi:10.4230/LIPIcs.ICALP.2023.32.
LibreCat: /record/32407
DOI: 10.4230/LIPIcs.ICALP.2023.32
arXiv: 2207.10250

Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture.”10.1137/22m1513721__SIAM Journal on Computing, vol. 52, no. 4, Society for Industrial &; Applied Mathematics (SIAM), 2023, pp. 1009–38, doi:10.1137/22m1513721.
LibreCat: /record/50271
DOI: 10.1137/22m1513721

Gharibian, Sevag, et al. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).”10.1007/s00037-022-00231-8__Computational Complexity, vol. 31, no. 2, 13, Springer Science and Business Media LLC, 2022, doi:10.1007/s00037-022-00231-8.
LibreCat: /record/34700
DOI: 10.1007/s00037-022-00231-8

Gharibian, Sevag, and Dorian Rudolph. “On Polynomially Many Queries to NP or QMA Oracles.”10.4230/LIPIcs.ITCS.2022.75__13th Innovations in Theoretical Computer Science (ITCS 2022), vol. 215, no. 75, 2022, pp. 1–27, doi:10.4230/LIPIcs.ITCS.2022.75.
LibreCat: /record/27160
DOI: 10.4230/LIPIcs.ITCS.2022.75

Gharibian, Sevag, and François Le Gall. “Dequantizing the Quantum Singular Value Transformation: Hardness and  Applications to Quantum Chemistry and the Quantum PCP Conjecture.” Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 2022, pp. 19–32.
LibreCat: /record/27531
arXiv: 2111.09079

Broadbent, Anne, et al. “Towards Quantum One-Time Memories from Stateless Hardware.”10.22331/q-2021-04-08-429__Quantum, vol. 5, 429, Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften, 2021, doi:10.22331/q-2021-04-08-429.
LibreCat: /record/29780
DOI: 10.22331/q-2021-04-08-429

Broadbent, Anne, et al. “Towards Quantum One-Time Memories from Stateless Hardware.” Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), vol. 158, Leibniz International Proceedings in Informatics (LIPIcs), 2020, p. 6:1-6:25.
LibreCat: /record/8426
arXiv: 1810.05226

Gharibian, Sevag, et al. “On Efficiently Solvable Cases of Quantum K-SAT.” Communications in Mathematical Physics, 2020.
LibreCat: /record/16927
arXiv: 1712.09617

Gharibian, Sevag, et al. “Oracle Complexity Classes and Local Measurements on Physical  Hamiltonians.” Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, p. 38.
LibreCat: /record/13226
arXiv: 1909.05981

Gharibian, Sevag, and Ojas Parekh. “Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut.”10.4230/LIPICS.APPROX-RANDOM.2019.31__Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), vol. 145, 2019, p. 31:1-31:17, doi:10.4230/LIPICS.APPROX-RANDOM.2019.31.
LibreCat: /record/13297
DOI: 10.4230/LIPICS.APPROX-RANDOM.2019.31

Gharibian, Sevag, and Justin Yirka. “The Complexity of Simulating Local Measurements on Quantum Systems.”10.22331/q-2019-09-30-189__Quantum, vol. 3, 2019, p. 189, doi:10.22331/q-2019-09-30-189.
LibreCat: /record/13558
DOI: 10.22331/q-2019-09-30-189

Aldi, Marco, et al. “On Efficiently Solvable Cases of Quantum K-SAT.”10.4230/LIPIcs.MFCS.2018.38__43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 38:1-38:16, doi:10.4230/LIPIcs.MFCS.2018.38.
LibreCat: /record/8162
DOI: 10.4230/LIPIcs.MFCS.2018.38
arXiv: 1712.09617

Gharibian, Sevag, et al. “Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2).”10.4230/LIPIcs.MFCS.2018.58__43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018), edited by Igor Potapov et al., vol. 117, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, p. 58:1-58:16, doi:10.4230/LIPIcs.MFCS.2018.58.
LibreCat: /record/8161
DOI: 10.4230/LIPIcs.MFCS.2018.58
arXiv: 1805.11139