A. Broadbent, S. Gharibian and H.-S. Zhou. Towards quantum one-time memories from stateless hardware. Proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020), volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1-6:25, 2020. Invited talk at 18th Asian Quantum Information Science Conference (AQIS 2018) Satellite Workshop on Quantum Computing, Kyoto University, Japan, 2018. Open access full version here.
S. Gharibian, S. Piddock and J. Yirka. Oracle complexity classes and local measurements on physical Hamiltonians. Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), volume 154 of Leibniz International Proceedings in Informatics (LIPIcs), 20:1--20:37, 2020. Also presented at 23rd Annual Conference on Quantum Information Processing (QIP 2020). Preliminary version presented at 18th Asian Quantum Information Science Conference (AQIS), 2018, by J. Yirka. Open access full version here.
S. Gharibian, O. Parekh. 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), volume 145 of Leibniz International Proceedings in Informatics (LIPIcs), pages 31:1-31:17, 2019. Also presented at 23rd Annual Conference on Quantum Information Processing (QIP 2020). Open access full version here.
S. Gharibian, M. Santha, J. Sikora, A. Sundaram and J. Yirka. Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1-58:16, 2018. Also presented as plenary talk (top 7% of submissions) at the 18th Asian Quantum Information Science Conference (AQIS 2018), and as invited talk by A. Sundaram at Quantum Innovators Workshop, IQC, University of Waterloo. Open access full version here.
M. Aldi, N. de Beaudrap, S. Gharibian and S. Saeedi. On efficiently solvable cases of Quantum k-SAT. Proceedings of 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), volume 117 of Leibniz International Proceedings in Informatics (LIPIcs), pages 38:1-38:16, 2018. Journal version to appear in Communications in Mathematical Physics, 2020. Presented as plenary talk (top 7% of submissions) at the 18th Asian Quantum Information Science Conference (AQIS 2018). Open access full version here.
S. Gharibian and J. Yirka. The complexity of simulating local measurements on quantum systems. Proceedings of the 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017), volume 73 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1-2:17, 2018. Journal version in Quantum, 3:189, 2019. Also presented as poster by Justin Yirka at QIP 2017. Video from talk at Leibniz Universität Hannover is available here.
N. de Beaudrap and S. Gharibian. A linear time algorithm for quantum 2-SAT. In Proceedings of the 31st Conference on Computational Complexity (CCC), volume 50 of Leibniz International Proceedings in Informatics (LIPIcs), pages 27:1-27:21, 2016. Also presented at the 19th Conference on Quantum Information Processing (QIP), 2016. Open access full version here.
S. Gharibian, Y. Huang, and Z. Landau, S. W. Shin. Quantum Hamiltonian Complexity. Foundations and Trends in Theoretical Computer Science, 10(3):159-282, 2015. Open access full version here.
S. Gharibian, J. Sikora. Ground state connectivity of local Hamiltonians. In Proceedings of the 42nd International Colloquium on Automata, Languages and Programming (ICALP), volume 9134 of Lecture Notes in Computer Science, pages 617 – 628, 2015. Full version in ACM Transactions on Computation Theory, volume 10, issue 2, 2018. Open access full version here.
S. Gharibian, Z. Landau, S. W. Shin, and G. Wang. Tensor network non-zero testing. Quantum Information & Computation 15 (9 & 10):885-899, 2015. Presented by S. W. Shin as long talk at AQIS 2014. Open access full version here.
S. Gharibian and J. Kempe. Hardness of approximation for quantum problems. Quantum Information & Computation 14 (5 & 6), 2014. Invited talk at ELC Workshop on Inapproximability, University of Electro-Communications, Japan. Also presented at QIP 2012, ICALP 2012. Open access full version here.
S. Gharibian and J. Kempe. Approximation algorithms for QMA-complete problems, SIAM Journal on Computing 41(4): 1028-1050, 2012. Presented at CCC 2011. Winner of Best Poster Award at QIP 2011. Open access full version here.
S. Gharibian. Strong NP-hardness of the quantum separability problem, Quantum Information & Computation 10(3 & 4): 343-360, 2010. Winner of 2nd Place for Best Speaker Award, CQISC 2008. Also presented at SQuInT 2009. Open access full version here.
