activity
20092026
most citedOn Necessary and Sufficient Number of Cops in the Game of Cops and Robber in Multidimensional Grids

16 citations · 26 across the 13 of their papers we have counts for

collaborators
Showing 2017Show all

2 papers · 1 filter

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…