67 citations · 111 across the 12 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2018★ 10 cited
Quantum generalizations of the polynomial hierarchy with applications to QMA(2)
Sevag Gharibian, Miklos Santha, Jamie Sikora +2
The polynomial-time hierarchy () has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as $\m…
cs.CC2016
On the complexity of probabilistic trials for hidden satisfiability problems
Itai Arad, Adam Bouland, Daniel Grier +3
What is the minimum amount of information and time needed to solve 2SAT? When the instance is known, it can be solved in polynomial time, but is this also possible without knowing…
cs.CC2014
On the Complexity of Trial and Error for Constraint Satisfaction Problems
Gábor Ivanyos, Raghav Kulkarni, Youming Qiao +2
In 2013 Bei, Chen and Zhang introduced a trial and error model of computing, and applied to some constraint satisfaction problems. In this model the input is hidden by an oracle wh…