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
A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, in: SIAM Symposium on Simplicity in Algorithms (SOSA), n.d., pp. 247–253.
LibreCat | arXiv
 

2026 | Conference Paper | LibreCat-ID: 57866
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), 2026, p. 7:1-7:24.
LibreCat | arXiv
 

2026 | Conference Paper | LibreCat-ID: 56950
Hardness of approximation for ground state problems
S. Gharibian, C. Hecht, in: 51st International Symposium on Mathematical Foundations of Computer Science (MFCS), n.d.
LibreCat | arXiv
 

2026 | Conference Paper | LibreCat-ID: 61777
How hard is it to verify a classical shadow?
G. Karaiskos, D. Rudolph, J.J. Meyer, J. Eisert, S. Gharibian, in: International Colloquium on Automata, Languages, and Programming (ICALP), 2026, pp. 1–23.
LibreCat | arXiv
 

2025 | Preprint | LibreCat-ID: 61778
On the complexity of estimating ground state entanglement and free energy
S. Gharibian, J. Kamminga, ArXiv:2510.06796 (2025).
LibreCat | arXiv
 

2025 | Conference Paper | LibreCat-ID: 50272
Quantum 2-SAT on low dimensional systems is $\mathsf{QMA}_1$-complete: Direct embeddings and black-box simulation
D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24.
LibreCat | DOI | arXiv
 

2025 | Journal Article | LibreCat-ID: 55037
Beating Grover search for low-energy estimation and state preparation
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, Physical Review Letters 135 (2025) 030601.
LibreCat | DOI | arXiv
 

2025 | Preprint | LibreCat-ID: 61776
Energy, Bosons and Computational Complexity
U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H.R. Naeij, D. Rudolph, D. Sambrani, ArXiv:2510.08545 (2025).
LibreCat | arXiv
 

2025 | Preprint | LibreCat-ID: 60432
Quantum k-SAT Related Hypergraph Problems
S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
LibreCat | arXiv
 

2024 | Conference Paper | LibreCat-ID: 50273
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
A. Agarwal, S. Gharibian, V. Koppula, D. Rudolph, in: Proceedings of 49th International Symposium on Mathematical Foundations of Computer Science (MFCS), 2024, pp. 7–17.
LibreCat | DOI | arXiv
 

2024 | Conference Paper | LibreCat-ID: 50406
BQP, meet NP: Search-to-decision reductions and approximate counting
S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024, pp. 1–19.
LibreCat | arXiv
 

2024 | Preprint | LibreCat-ID: 56944
Second order cone relaxations for quantum Max Cut
F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
LibreCat | arXiv
 

2024 | Journal Article | LibreCat-ID: 48544 | OA
Guest Column: The 7 faces of quantum NP
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
LibreCat | Files available | Download (ext.)
 

2023 | Conference Paper | LibreCat-ID: 32407
Improved Hardness Results for the Guided Local Hamiltonian Problem
S. Gharibian, R. Hayakawa, F.L. Gall, T. Morimae, in: Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2023, pp. 1–19.
LibreCat | DOI | arXiv
 

2023 | Conference Paper | LibreCat-ID: 31872
Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement
S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science (ITCS), 2023, p. 53:1-53:23.
LibreCat | DOI | arXiv
 

2023 | Conference Paper | LibreCat-ID: 20841 | OA
The Complexity of Translationally Invariant Problems beyond Ground State Energies
S. Gharibian, J. Watson, J. Bausch, in: Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 2023, p. 54:1-54:21.
LibreCat | DOI | Download (ext.) | arXiv
 

2023 | Conference Paper | LibreCat-ID: 34138
The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate
L. Bittel, S. Gharibian, M. Kliesch, in: Proceedings of the 38th Computational Complexity Conference (CCC), 2023, p. 34:1-34:24.
LibreCat | DOI | arXiv
 

2023 | Journal Article | LibreCat-ID: 50271
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
S. Gharibian, F. Le Gall, SIAM Journal on Computing 52 (2023) 1009–1038.
LibreCat | DOI
 

2022 | Conference Paper | LibreCat-ID: 27531 | OA
Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture
S. Gharibian, F.L. Gall, in: Proceedings of the 54th ACM Symposium on Theory of Computing (STOC), 2022, pp. 19–32.
LibreCat | Download (ext.) | arXiv
 

2022 | Journal Article | LibreCat-ID: 34700
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
S. Gharibian, M. Santha, J. Sikora, A. Sundaram, J. Yirka, Computational Complexity 31 (2022).
LibreCat | DOI
 

Filters and Search Terms

(person=71541)

Search

Filter Publications

Display / Sort

Export / Embed