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.

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.

Hardness of approximation for ground state problems
S. Gharibian, C. Hecht, in: 51st International Symposium on Mathematical Foundations of Computer Science (MFCS), n.d.

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.

On the complexity of estimating ground state entanglement and free  energy
S. Gharibian, J. Kamminga, ArXiv:2510.06796 (2025).

Quantum 2-SAT on low dimensional systems is $\'6dathsfQMA_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.

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.

Energy, Bosons and Computational Complexity
U. Chabaud, S. Gharibian, S. Mehraban, A. Motamedi, H.R. Naeij, D. Rudolph, D. Sambrani, ArXiv:2510.08545 (2025).

Quantum k-SAT Related Hypergraph Problems
S.-L. Kremer, D. Rudolph, S. Gharibian, ArXiv:2506.17066 (2025).

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.

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.

Second order cone relaxations for quantum Max Cut
F. Huber, K. Thompson, O. Parekh, S. Gharibian, ArXiv:2411.04120 (2024).

Guest Column: The 7 faces of quantum NP
S. Gharibian, ACM SIGACT News 54 (2024) 54–91.

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.

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.

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.

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.

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.

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.

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).