24 citations · 57 across the 20 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.CC2017★ 2 cited
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…
cs.CC2017
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…
cs.CC2017★ 1 cited
A Composition Theorem for Randomized Query Complexity
Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5
Let the randomized query complexity of a relation for error probability be denoted by . We prove that for any relation an…