22 citations · 121 across the 26 of their papers we have counts for
35 papers
Bare quantum simultaneity versus classical interactivity in communication complexity
Dmytro Gavinsky
A relational bipartite communication problem is presented that has an efficient quantum simultaneous-messages protocol, but no efficient classical two-way protocol.
Santha-Vazirani sources, deterministic condensers and very strong extractors
Dmytro Gavinsky, Pavel Pudlák
The notion of semi-random sources, also known as Santha-Vazirani (SV) sources, stands for a sequence of n bits, where the dependence of the i'th bit on the previous i-1 bits is lim…
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…
The layer complexity of Arthur-Merlin-like communication
D. Gavinsky
In communication complexity the Arthur-Merlin (AM) model is the most natural one that allows both randomness and non-determinism. Presently we do not have any super-logarithmic low…
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…
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…