Sevag Gharibian

69 papers A* 3A 9B 3Journal 47Unranked 7

Year	Rank	Type	Title / Venue / Authors
2026	—	`conf`	A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. SOSA Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2026	A	`conf`	An Unholy Trinity: TFNP, Polynomial Systems, and the Quantum Satisfiability Problem. ITCS Marco Aldi, Sevag Gharibian, Dorian Rudolph
2025	J	`jnl`	A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT. CoRR Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2025	J	`jnl`	An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem. Electron. Colloquium Comput. Complex. Marco Aldi, Sevag Gharibian, Dorian Rudolph
2025	J	`jnl`	How hard is it to verify a classical shadow? CoRR Georgios Karaiskos, Dorian Rudolph, Johannes Jakob Meyer, Jens Eisert, Sevag Gharibian
2025	J	`jnl`	On the complexity of estimating ground state entanglement and free energy. CoRR Sevag Gharibian, Jonas Kamminga
2025	A	`conf`	Quantum 2-SAT on Low Dimensional Systems Is QMAsubscript{1}-Complete: Direct Embeddings and Black-Box Simulation. ITCS Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
2025	J	`jnl`	Quantum k-SAT Related Hypergraph Problems. CoRR Simon-Luca Kremer, Dorian Rudolph, Sevag Gharibian
2024	J	`jnl`	An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem. CoRR Marco Aldi, Sevag Gharibian, Dorian Rudolph
2024	A*	`conf`	BQP, Meet NP: Search-To-Decision Reductions and Approximate Counting. ICALP Sevag Gharibian, Jonas Kamminga
2024	J	`jnl`	BQP, meet NP: Search-to-decision reductions and approximate counting. CoRR Sevag Gharibian, Jonas Kamminga
2024	J	`jnl`	Beating Grover search for low-energy estimation and state preparation. CoRR Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, Suguru Tamaki
2024	J	`jnl`	Hardness of approximation for ground state problems. CoRR Sevag Gharibian, Carsten Hecht
2024	J	`jnl`	Quantum 2-SAT on low dimensional systems is QMA CoRR Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
2024	B	`conf`	Quantum Polynomial Hierarchies: Karp-Lipton, Error Reduction, and Lower Bounds. MFCS Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph
2024	J	`jnl`	Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds. CoRR Avantika Agarwal, Sevag Gharibian, Venkata Koppula, Dorian Rudolph
2023	J	`jnl`	Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. SIAM J. Comput. Sevag Gharibian, François Le Gall
2023	J	`jnl`	Guest Column: The 7 faces of quantum NP. SIGACT News Sevag Gharibian
2023	A*	`conf`	Improved Hardness Results for the Guided Local Hamiltonian Problem. ICALP Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae, Jordi Weggemans
2023	A	`conf`	Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover Interactive Proofs into Unentanglement. ITCS Sevag Gharibian, Dorian Rudolph
2023	J	`jnl`	The 7 faces of quantum NP. CoRR Sevag Gharibian
2023	A	`conf`	The Complexity of Translationally Invariant Problems Beyond Ground State Energies. STACS James D. Watson, Johannes Bausch, Sevag Gharibian
2023	A	`conf`	The Optimal Depth of Variational Quantum Algorithms Is QCMA-Hard to Approximate. CCC Lennart Bittel, Sevag Gharibian, Martin Kliesch
2022	A*	`conf`	Dequantizing the Quantum singular value transformation: hardness and applications to Quantum chemistry and the Quantum PCP conjecture. STOC Sevag Gharibian, François Le Gall
2022	J	`jnl`	Improved Hardness Results for the Guided Local Hamiltonian Problem. CoRR Sevag Gharibian, Ryu Hayakawa, François Le Gall, Tomoyuki Morimae
2022	A	`conf`	On Polynomially Many Queries to NP or QMA Oracles. ITCS Sevag Gharibian, Dorian Rudolph
2022	J	`jnl`	Optimizing the depth of variational quantum algorithms is strongly QCMA-hard to approximate. CoRR Lennart Bittel, Sevag Gharibian, Martin Kliesch
2022	J	`jnl`	Quantum generalizations of the polynomial hierarchy with applications to QMA(2). Comput. Complex. Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
2022	J	`jnl`	Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement. CoRR Sevag Gharibian, Dorian Rudolph
2021	J	`jnl`	Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjecture. CoRR Sevag Gharibian, François Le Gall
2021	J	`jnl`	On polynomially many queries to NP or QMA oracles. CoRR Sevag Gharibian, Dorian Rudolph
2021	J	`jnl`	On polynomially many queries to NP or QMA oracles. Electron. Colloquium Comput. Complex. Sevag Gharibian, Dorian Rudolph
2021	J	`jnl`	Quantum Complexity: Theory and Application (Dagstuhl Seminar 21261). Dagstuhl Reports Bill Fefferman, Sevag Gharibian, Norbert Schuch, Barbara M. Terhal
2021	J	`jnl`	Towards Quantum One-Time Memories from Stateless Hardware. Quantum Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou
2020	A	`conf`	Oracle Complexity Classes and Local Measurements on Physical Hamiltonians. STACS Sevag Gharibian, Stephen Piddock, Justin Yirka
2020	J	`jnl`	The Complexity of Translationally Invariant Problems beyond Ground State Energies. CoRR James D. Watson, Johannes Bausch, Sevag Gharibian
2020	—	`conf`	Towards Quantum One-Time Memories from Stateless Hardware. TQC Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou
2019	—	`conf`	Almost Optimal Classical Approximation Algorithms for a Quantum Generalization of Max-Cut. APPROX-RANDOM Sevag Gharibian, Ojas Parekh
2019	J	`jnl`	Almost optimal classical approximation algorithms for a quantum generalization of Max-Cut. CoRR Sevag Gharibian, Ojas Parekh
2019	J	`jnl`	Oracle complexity classes and local measurements on physical Hamiltonians. CoRR Sevag Gharibian, Stephen Piddock, Justin Yirka
2019	J	`jnl`	The complexity of simulating local measurements on quantum systems. Quantum Sevag Gharibian, Justin Yirka
2018	J	`jnl`	Ground State Connectivity of Local Hamiltonians. ACM Trans. Comput. Theory Sevag Gharibian, Jamie Sikora
2018	B	`conf`	On Efficiently Solvable Cases of Quantum k-SAT. MFCS Marco Aldi, Niel de Beaudrap, Sevag Gharibian, Seyran Saeedi
2018	B	`conf`	Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). MFCS Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
2018	J	`jnl`	Quantum generalizations of the polynomial hierarchy with applications to QMA(2). CoRR Sevag Gharibian, Miklos Santha, Jamie Sikora, Aarthi Sundaram, Justin Yirka
2018	J	`jnl`	Towards Quantum One-Time Memories from Stateless Hardware. IACR Cryptol. ePrint Arch. Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou
2017	J	`jnl`	On efficiently solvable cases of Quantum k-SAT. CoRR Marco Aldi, Niel de Beaudrap, Sevag Gharibian, Seyran Saeedi
2017	—	`conf`	The Complexity of Simulating Local Measurements on Quantum Systems. TQC Sevag Gharibian, Justin Yirka
2016	A	`conf`	A Linear Time Algorithm for Quantum 2-SAT. CCC J. Niel de Beaudrap, Sevag Gharibian
2016	J	`jnl`	The complexity of estimating local physical quantities. CoRR Sevag Gharibian, Justin Yirka
2015	J	`jnl`	A linear time algorithm for quantum 2-SAT. CoRR Niel de Beaudrap, Sevag Gharibian
2015	—	`conf`	Ground State Connectivity of Local Hamiltonians. ICALP (1) Sevag Gharibian, Jamie Sikora
2015	J	`jnl`	Quantum Hamiltonian Complexity. Found. Trends Theor. Comput. Sci. Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin
2015	J	`jnl`	Tensor network non-zero testing. Quantum Inf. Comput. Sevag Gharibian, Zeph Landau, Seung Woo Shin, Guoming Wang
2014	J	`jnl`	Gate-efficient discrete simulations of continuous-time quantum query algorithms. Quantum Inf. Comput. Dominic W. Berry, Richard Cleve, Sevag Gharibian
2014	J	`jnl`	Ground state connectivity of local Hamiltonians. CoRR Sevag Gharibian, Jamie Sikora
2014	J	`jnl`	Hardness of approximation for quantum problems. Quantum Inf. Comput. Sevag Gharibian, Julia Kempe
2014	J	`jnl`	Quantum Hamiltonian Complexity. CoRR Sevag Gharibian, Yichen Huang, Zeph Landau
2014	J	`jnl`	Tensor network non-zero testing. CoRR Sevag Gharibian, Zeph Landau, Seung Woo Shin, Guoming Wang
2013	J	`jnl`	QMA variants with polynomially many provers. Quantum Inf. Comput. Sevag Gharibian, Jamie Sikora, Sarvagya Upadhyay
2012	J	`jnl`	Approximation Algorithms for QMA-Complete Problems. SIAM J. Comput. Sevag Gharibian, Julia Kempe
2012	—	`conf`	Hardness of Approximation for Quantum Problems. ICALP (1) Sevag Gharibian, Julia Kempe
2012	J	`jnl`	Hardness of approximation for quantum problems CoRR Sevag Gharibian, Julia Kempe
2011	A	`conf`	Approximation Algorithms for QMA-Complete Problems. CCC Sevag Gharibian, Julia Kempe
2011	J	`jnl`	Approximation algorithms for QMA-complete problems CoRR Sevag Gharibian, Julia Kempe
2011	J	`jnl`	QMA variants with polynomially many provers CoRR Sevag Gharibian, Jamie Sikora, Sarvagya Upadhyay
2010	J	`jnl`	Strong NP-hardness of the quantum separability problem. Quantum Inf. Comput. Sevag Gharibian
2009	J	`jnl`	On global effects caused by locally noneffective unitary operations. Quantum Inf. Comput. Sevag Gharibian, Hermann Kampermann, Dagmar Bruß
2009	—	`conf`	Revealing Quantum Entanglement via Locally Noneffective Operations. QI Dagmar Bruß, Sevag Gharibian, Hermann Kampermann