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.
52 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
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.
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
M. Aldi, S. Gharibian, D. Rudolph, in: 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), 2026, p. 7:1-7:24.
2026 | Preprint | LibreCat-ID: 67088
Semidefinite extension complexity of the separable set, with applications to approximate disentanglers
S. Gharibian, C. Hecht, D. Rudolph, ArXiv:2609.09033 (n.d.).
LibreCat
| arXiv
S. Gharibian, C. Hecht, D. Rudolph, ArXiv:2609.09033 (n.d.).
2026 | Preprint | LibreCat-ID: 67292
Verification Complexity and Extension of Classical Shadows
G. Karaiskos, A. Raza, D. Rudolph, D.E. Koh, S. Gharibian, ArXiv:2609.40107 (2026).
LibreCat
| arXiv
G. Karaiskos, A. Raza, D. Rudolph, D.E. Koh, S. Gharibian, ArXiv:2609.40107 (2026).
2026 | Preprint | LibreCat-ID: 67293
Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
S. Gharibian, F. Le Gall, R. Mataraarachchi, S. Tamaki, (2026).
LibreCat
S. Gharibian, F. Le Gall, R. Mataraarachchi, S. Tamaki, (2026).
2026 | Preprint | LibreCat-ID: 67291
A physical and universal model of bosonic computations with Solovay-Kitaev theorem
D. Rudolph, A. Motamedi, D. Sambrani, H. Reza Naeij, U. Chabaud, S. Gharibian, S. Mehraban, (n.d.).
LibreCat
D. Rudolph, A. Motamedi, D. Sambrani, H. Reza Naeij, U. Chabaud, S. Gharibian, S. Mehraban, (n.d.).
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
G. Karaiskos, D. Rudolph, J.J. Meyer, J. Eisert, S. Gharibian, in: International Colloquium on Automata, Languages, and Programming (ICALP), 2026, pp. 1–23.
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., pp. 1–19.
LibreCat
| arXiv
S. Gharibian, C. Hecht, in: 51st International Symposium on Mathematical Foundations of Computer Science (MFCS), n.d., pp. 1–19.
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
S. Gharibian, J. Kamminga, ArXiv:2510.06796 (2025).
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
D. Rudolph, S. Gharibian, D. Nagaj, in: 16th Innovations in Theoretical Computer Science (ITCS), 2025, pp. 1–24.
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
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, Physical Review Letters 135 (2025) 030601.
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
U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H.R. Naeij, D. Rudolph, D. Sambrani, ArXiv:2510.08545 (2025).
2025 | Preprint | LibreCat-ID: 60432
Quantum k-SAT Related Hypergraph Problems
S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
LibreCat
| arXiv
S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).
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
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.
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
S. Gharibian, J. Kamminga, in: Proceedings of 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP), 2024, pp. 1–19.
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
F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).
2024 | Journal Article | LibreCat-ID: 48544 | 
Guest Column: The 7 faces of quantum NP
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
LibreCat
| Files available
| Download (ext.)
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.
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
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.
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
S. Gharibian, D. Rudolph, in: 14th Innovations in Theoretical Computer Science (ITCS), 2023, p. 53:1-53:23.
2023 | Conference Paper | LibreCat-ID: 20841 |
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
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.