225 citations · 582 across the 52 of their papers we have counts for
14 papers · 1 filter
On the cut dimension of a graph
Troy Lee, Tongyang Li, Miklos Santha +1
Let be a weighted undirected graph with edges. The cut dimension of is the dimension of the span of the characteristic vectors of the minimum cuts of , viewe…
A composition theorem for randomized query complexity via max conflict complexity
Dmitry Gavinsky, Troy Lee, Miklos Santha +1
Let stand for the bounded-error randomized query complexity with error . For any relation and partial Boolean function $g \subse…
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…
On the randomised query complexity of composition
Dmytro Gavinsky, Troy Lee, Miklos Santha
Let be a relation and be a promise function. This work investigates the randomised query complexity of the relation $f\circ g…
On the Polynomial Parity Argument Complexity of the Combinatorial Nullstellensatz
Aleksandrs Belovs, Gábor Ivanyos, Youming Qiao +2
The complexity class PPA consists of NP-search problems which are reducible to the parity principle in undirected graphs. It contains a wide variety of interesting problems from gr…
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
Let be a Boolean function. The certificate complexity is a complexity measure that is quadratically tight for the zero-error randomized que…