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 cs.DMShow all

2 papers · 1 filter

cs.DM2015★ 1 cited

On the Joint Entropy of $d$ -Wise-Independent Variables

Dmytro Gavinsky, Pavel Pudlák

How low can the joint entropy of $n$ $d$ -wise independent (for $d \geq 2$ ) discrete random variables be, subject to given constraints on the individual distributions (say, no value ma…

cs.DM2012★ 1 cited

A Tail Bound for Read-k Families of Functions

Dmytro Gavinsky, Shachar Lovett, Michael Saks +1

We prove a Chernoff-like large deviation bound on the sum of non-independent random variables that have the following dependence structure. The variables $Y_{1}, ..., Y_{r}$ are arbitrar…

On the Joint Entropy of d-Wise-Independent Variables

A Tail Bound for Read-k Families of Functions

On the Joint Entropy of $d$ -Wise-Independent Variables