ELC Seminar (C01)
Date: July 2nd
Time: 13:30-14:30
Place: CELC Seminar room (Rm.404)

Speaker: Jaikumar Radhakrishnan
(Tata Institute of Fundamental Research)
Title: Communication assisted agreement distillation

Abstract: Bogdanov and Mossel (2011) consider the following problem.

"Suppose Alice receives a string of unbiased independent random bits
and Bob receives a noisy copy of the same bits, where each bit is
flipped with probability eps < 1/2. Alice and Bob wish to extract a
common sequence of k random bits."

Bogdanov and Mossel show that for any strategy where Alice and Bob,
with no communication, produce k uniformly distributed bits, the
probability that their outputs agree is at most $2^{- k
eps/(1-eps)}$. Furthermore, they show that the bound is tight by
exhibiting a strategy for Alice and Bob, where their outputs agree
with probability at least $2^{-k eps/(1-eps) - O(log k)}$. Note that
this strategy does better than the natural strategy where Alice and
Bob just use their first k bits (which agree with probability
(1-eps)^k).

We study the relationship between communication and probability of
agreement. Suppose Alice wishes to send Bob a message of delta k bits
to ensure their k-bit outputs agree with probability 2^{-gamma k}. How
big must delta be as a function of gamma? We show the following:

     delta(gamma) >= C (1-gamma) - 2 sqrt{C(1-C) gamma}.

where C = 4 eps (1-eps).

This implies that that for delta(gamma) = 0, we have gamma >=
eps/(1-eps), thus recovering the the above mentioned result of
Bogdanov and Mossel for zero communication.  Also, if Alice and Bob
wish to agree with constant probability (say 1/2), then Alice must
send about 4 eps (1-eps) k bits; this slightly improves a result of
Canonne, Meka, Sudan and Guruswami (2014), who showed that at least
eps k bits of communication are necessary. We also obtain strategies
that show that this trade-off between communication and probability of
error above is asymptotically tight. This result can also be used to
recovers similar results obtained by Chandar and Tchamkerten (2014) in
the regime when the error probability is assumed to go to zero.

In this talk, we will describe the above trade-off, which is based on
the standard hypercontractivity inequality. We will also outline the
protocols that achieve this trade-off.

(This is part of joint work with Venkat Guruswami.)