Please note that LibreCat no longer supports Internet Explorer versions 8 or 9 (or earlier).
We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox.
48 Publications
2026 | Conference Paper | LibreCat-ID: 61922
@inproceedings{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki, title={A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT}, booktitle={SIAM Symposium on Simplicity in Algorithms (SOSA)}, author={Buhrman, Harry and Gharibian, Sevag and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}, pages={247–253} }
LibreCat
| arXiv
2026 | Conference Paper | LibreCat-ID: 57866
@inproceedings{Aldi_Gharibian_Rudolph_2026, title={An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem}, volume={362}, booktitle={17th Innovations in Theoretical Computer Science Conference (ITCS 2026)}, author={Aldi, Marco and Gharibian, Sevag and Rudolph, Dorian}, year={2026}, pages={7:1-7:24} }
LibreCat
| arXiv
2026 | Conference Paper | LibreCat-ID: 61777
@inproceedings{Karaiskos_Rudolph_Meyer_Eisert_Gharibian_2026, title={How hard is it to verify a classical shadow?}, volume={374}, number={123}, booktitle={International Colloquium on Automata, Languages, and Programming (ICALP)}, author={Karaiskos, Georgios and Rudolph, Dorian and Meyer, Johannes Jakob and Eisert, Jens and Gharibian, Sevag}, year={2026}, pages={1–23} }
LibreCat
| arXiv
2025 | Conference Paper | LibreCat-ID: 50272
@inproceedings{Rudolph_Gharibian_Nagaj_2025, title={Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation}, volume={325}, DOI={10.4230/LIPIcs.ITCS.2025.85}, number={85}, booktitle={16th Innovations in Theoretical Computer Science (ITCS)}, author={Rudolph, Dorian and Gharibian, Sevag and Nagaj, Daniel}, year={2025}, pages={1–24} }
LibreCat
| DOI
| arXiv
2025 | Journal Article | LibreCat-ID: 55037
@article{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki_2025, title={Beating Grover search for low-energy estimation and state preparation}, volume={135}, DOI={10.1103/29qw-bssx}, journal={Physical Review Letters}, author={Buhrman, Harry and Gharibian, Sevag and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}, year={2025}, pages={030601} }
LibreCat
| DOI
| arXiv
2025 | Preprint | LibreCat-ID: 61776
@article{Chabaud_Gharibian_Mehraban_Motamedi_Naeij_Rudolph_Sambrani_2025, title={Energy, Bosons and Computational Complexity}, journal={arXiv:2510.08545}, author={Chabaud, Ulysse and Gharibian, Sevag and Mehraban, Saeed and Motamedi, Arsalan and Naeij, Hamid Reza and Rudolph, Dorian and Sambrani, Dhruva}, year={2025} }
LibreCat
| arXiv
2024 | Conference Paper | LibreCat-ID: 50273
@inproceedings{Agarwal_Gharibian_Koppula_Rudolph_2024, title={Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds}, volume={306}, DOI={10.4230/LIPIcs.MFCS.2024.7}, number={7}, booktitle={Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS)}, author={Agarwal, Avantika and Gharibian, Sevag and Koppula, Venkata and Rudolph, Dorian}, year={2024}, pages={7–17} }
LibreCat
| DOI
| arXiv
2024 | Conference Paper | LibreCat-ID: 50406
@inproceedings{Gharibian_Kamminga_2024, title={BQP, meet NP: Search-to-decision reductions and approximate counting}, volume={297}, number={70}, booktitle={Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and Kamminga, Jonas}, year={2024}, pages={1–19} }
LibreCat
| arXiv
2024 | Journal Article | LibreCat-ID: 48544 | 
@article{Gharibian_2024, title={Guest Column: The 7 faces of quantum NP}, volume={54}, number={4}, journal={ACM SIGACT News}, author={Gharibian, Sevag}, year={2024}, pages={54–91} }
LibreCat
| Files available
| Download (ext.)
2023 | Conference Paper | LibreCat-ID: 32407
@inproceedings{Gharibian_Hayakawa_Gall_Morimae_2023, title={Improved Hardness Results for the Guided Local Hamiltonian Problem}, volume={261}, DOI={10.4230/LIPIcs.ICALP.2023.32}, number={32}, booktitle={Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP)}, author={Gharibian, Sevag and Hayakawa, Ryu and Gall, François Le and Morimae, Tomoyuki}, year={2023}, pages={1–19} }
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 31872
@inproceedings{Gharibian_Rudolph_2023, title={Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement}, volume={251}, DOI={10.4230/LIPIcs.ITCS.2023.53}, booktitle={14th Innovations in Theoretical Computer Science (ITCS)}, author={Gharibian, Sevag and Rudolph, Dorian}, year={2023}, pages={53:1-53:23} }
LibreCat
| DOI
| arXiv
2023 | Conference Paper | LibreCat-ID: 20841 |
@inproceedings{Gharibian_Watson_Bausch_2023, title={The Complexity of Translationally Invariant Problems beyond Ground State Energies}, volume={254}, DOI={https://doi.org/10.4230/LIPIcs.STACS.2023.54}, booktitle={Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS)}, author={Gharibian, Sevag and Watson, James and Bausch, Johannes}, year={2023}, pages={54:1-54:21} }
LibreCat
| DOI
| Download (ext.)
| arXiv
2023 | Conference Paper | LibreCat-ID: 34138
@inproceedings{Bittel_Gharibian_Kliesch_2023, series={Leibniz International Proceedings in Informatics (LIPIcs)}, title={The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate}, volume={264}, DOI={10.4230/LIPIcs.CCC.2023.34}, number={34}, booktitle={Proceedings of the 38th Computational Complexity Conference (CCC)}, author={Bittel, Lennart and Gharibian, Sevag and Kliesch, Martin}, year={2023}, pages={34:1-34:24}, collection={Leibniz International Proceedings in Informatics (LIPIcs)} }
LibreCat
| DOI
| arXiv
2023 | Journal Article | LibreCat-ID: 50271
@article{Gharibian_Le Gall_2023, title={Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}, volume={52}, DOI={10.1137/22m1513721}, number={4}, journal={SIAM Journal on Computing}, publisher={Society for Industrial & Applied Mathematics (SIAM)}, author={Gharibian, Sevag and Le Gall, François}, year={2023}, pages={1009–1038} }
LibreCat
| DOI
2022 | Conference Paper | LibreCat-ID: 27531 |
@inproceedings{Gharibian_Gall_2022, title={Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture}, booktitle={Proceedings of the 54th ACM Symposium on Theory of Computing (STOC)}, author={Gharibian, Sevag and Gall, François Le}, year={2022}, pages={19–32} }
LibreCat
| Download (ext.)
| arXiv
2022 | Journal Article | LibreCat-ID: 34700
@article{Gharibian_Santha_Sikora_Sundaram_Yirka_2022, title={Quantum generalizations of the polynomial hierarchy with applications to QMA(2)}, volume={31}, DOI={10.1007/s00037-022-00231-8}, number={213}, journal={Computational Complexity}, publisher={Springer Science and Business Media LLC}, author={Gharibian, Sevag and Santha, Miklos and Sikora, Jamie and Sundaram, Aarthi and Yirka, Justin}, year={2022} }
LibreCat
| DOI