2 citations · 3 across the 8 of their papers we have counts for
3 papers · 1 filter
An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
Marco Aldi, Sevag Gharibian, Dorian Rudolph
The theory of Total Function NP (TFNP) and its subclasses says that, even if one is promised an efficiently verifiable proof exists for a problem, finding this proof can be intract…
Quantum 2-SAT on low dimensional systems is -complete: Direct embeddings and black-box simulation
Dorian Rudolph, Sevag Gharibian, Daniel Nagaj
Despite the fundamental role the Quantum Satisfiability (QSAT) problem has played in quantum complexity theory, a central question remains open: At which local dimension does the c…
Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
Avantika Agarwal, Sevag Gharibian, Venkata Koppula +1
The Polynomial-Time Hierarchy () is a staple of classical complexity theory, with applications spanning randomized computation to circuit lower bounds to ''quantum adv…