Dmitry Gavinsky

activity

20042019

most citedEntanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems

22 citations · 121 across the 26 of their papers we have counts for

collaborators

Showing 2018Show all

3 papers · 1 filter

cs.CC2018

A composition theorem for randomized query complexity via max conflict complexity

Dmitry Gavinsky, Troy Lee, Miklos Santha +1

Let $R_{ε} (\cdot)$ stand for the bounded-error randomized query complexity with error $ε > 0$ . For any relation $f \subseteq {0, 1}^{n} \times S$ and partial Boolean function $g \subse…

cs.CC2018★ 1 cited

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…

cs.CC2018★ 6 cited

On the randomised query complexity of composition

Dmytro Gavinsky, Troy Lee, Miklos Santha

Let $f \subseteq {0, 1}^{n} \times Ξ$ be a relation and $g : {0, 1}^{m} \to {0, 1, *}$ be a promise function. This work investigates the randomised query complexity of the relation $f\circ g…