Rudolph, D., Gharibian, S., &; Nagaj, D. (2024). Quantum 2-SAT on low dimensional systems is $\'6dathsfQMA_1$-complete:  Direct embeddings and black-box simulation. In arXiv:2401.02368.
LibreCat: /record/50272
arXiv: 2401.02368

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

Agarwal, A., Gharibian, S., Koppula, V., &; Rudolph, D. (2024). Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower  bounds. In arXiv:2401.01633.
LibreCat: /record/50273
arXiv: 2401.01633

Gharibian, S., &; Kamminga, J. (n.d.). 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, S., &; Rudolph, D. (2023). Quantum space, ground space traversal, and how to embed multi-prover  interactive proofs into unentanglement. 14th Innovations in Theoretical Computer Science (ITCS), 251, 53:1-53:23.https://doi.org/10.4230/LIPIcs.ITCS.2023.53 
LibreCat: /record/31872
DOI: 10.4230/LIPIcs.ITCS.2023.53
arXiv: 2206.05243

Gharibian, S., Watson, J., &; Bausch, J. (2023). The Complexity of Translationally Invariant Problems beyond Ground State Energies. Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science (STACS), 254, 54:1-54:21.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, L., Gharibian, S., &; Kliesch, M. (2023). The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. Proceedings of the 38th Computational Complexity Conference (CCC), 264(34), 34:1-34:24.https://doi.org/10.4230/LIPIcs.CCC.2023.34 
LibreCat: /record/34138
DOI: 10.4230/LIPIcs.CCC.2023.34
arXiv: 2211.12519

Gharibian, S., Hayakawa, R., Gall, F. L., &; Morimae, T. (2023). Improved Hardness Results for the Guided Local Hamiltonian Problem. Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP), 261(32), 1–19.https://doi.org/10.4230/LIPIcs.ICALP.2023.32 
LibreCat: /record/32407
DOI: 10.4230/LIPIcs.ICALP.2023.32
arXiv: 2207.10250

Gharibian, S., &; Le Gall, F. (2023). Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. SIAM Journal on Computing, 52(4), 1009–1038.https://doi.org/10.1137/22m1513721 
LibreCat: /record/50271
DOI: 10.1137/22m1513721

Gharibian, S., Santha, M., Sikora, J., Sundaram, A., &; Yirka, J. (2022). Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Computational Complexity, 31(2), Article 13.https://doi.org/10.1007/s00037-022-00231-8 
LibreCat: /record/34700
DOI: 10.1007/s00037-022-00231-8

Gharibian, S., &; Rudolph, D. (2022). On polynomially many queries to NP or QMA oracles. 13th Innovations in Theoretical Computer Science (ITCS 2022), 215(75), 1–27.https://doi.org/10.4230/LIPIcs.ITCS.2022.75 
LibreCat: /record/27160
DOI: 10.4230/LIPIcs.ITCS.2022.75

Gharibian, S., &; Gall, F. L. (2022). 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), 19–32.
LibreCat: /record/27531
arXiv: 2111.09079

Broadbent, A., Gharibian, S., &; Zhou, H.-S. (2021). Towards Quantum One-Time Memories from Stateless Hardware. Quantum, 5, Article 429.https://doi.org/10.22331/q-2021-04-08-429 
LibreCat: /record/29780
DOI: 10.22331/q-2021-04-08-429

Broadbent, A., Gharibian, S., &; Zhou, H.-S. (2020). Towards Quantum One-Time Memories from Stateless Hardware. Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC), 158, 6:1-6:25.
LibreCat: /record/8426
arXiv: 1810.05226

Gharibian, S., Aldi, M., de Beaudrap, N., &; Saeedi, S. (2020). On efficiently solvable cases of Quantum k-SAT. Communications in Mathematical Physics.
LibreCat: /record/16927
arXiv: 1712.09617

Gharibian, S., Piddock, S., &; Yirka, J. (2020). Oracle complexity classes and local measurements on physical  Hamiltonians. Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 38.
LibreCat: /record/13226
arXiv: 1909.05981

Gharibian, S., &; Parekh, O. (2019). Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. Proceedings of the 22nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 145, 31:1-31:17.https://doi.org/10.4230/LIPICS.APPROX-RANDOM.2019.31 
LibreCat: /record/13297
DOI: 10.4230/LIPICS.APPROX-RANDOM.2019.31

Gharibian, S., &; Yirka, J. (2019). The complexity of simulating local measurements on quantum systems. Quantum, 3, 189.https://doi.org/10.22331/q-2019-09-30-189 
LibreCat: /record/13558
DOI: 10.22331/q-2019-09-30-189

Aldi, M., de Beaudrap, N., Gharibian, S., &; Saeedi, S. (2018). On Efficiently Solvable Cases of Quantum k-SAT. In I. Potapov, P. Spirakis, &; J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018) (Vol. 117, p. 38:1-38:16). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.https://doi.org/10.4230/LIPIcs.MFCS.2018.38 
LibreCat: /record/8162
DOI: 10.4230/LIPIcs.MFCS.2018.38
arXiv: 1712.09617

Gharibian, S., Santha, M., Sikora, J., Sundaram, A., &; Yirka, J. (2018). Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In I. Potapov, P. Spirakis, &; J. Worrell (Eds.), 43rd International Symposium on Mathematical Foundations  of Computer Science (MFCS 2018) (Vol. 117, p. 58:1-58:16). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.https://doi.org/10.4230/LIPIcs.MFCS.2018.58 
LibreCat: /record/8161
DOI: 10.4230/LIPIcs.MFCS.2018.58
arXiv: 1805.11139