Event
CCSP Seminar: Sagnik Bhattacharya, "Shared Randomness in Arbitrarily Varying Channels"
Thursday, February 27, 2020
5:00 p.m.-6:30 p.m.
2168 AVW
Ajaykrishnan Nageswaran
301 405 3661
ajayk@umd.edu
http://ccsp.ece.umd.edu/
Shared Randomness in Arbitrarily Varying Channels
Sagnik Bhattacharya
University of Maryland
Abstract
We study an adversarial communication problem where sender Alice wishes to send a message m to receiver Bob over an arbitrarily varying channel (AVC) controlled by a malicious adversary James. We assume that Alice and Bob share randomness K unknown to James. Using K, Alice first encodes the message m to a codeword X and transmits it over the AVC. James knows the message m, the (randomized) codebook, and the codeword X. James then inputs a jamming state S to disrupt communication; we assume a state-deterministic AVC where S completely specifies the channel noise. Bob receives a noisy version Y of codeword X; it outputs a message estimate m using Y and the shared randomness K. We show that for AVCs that are 'adversary-weakened', exactly log(n) equiprobable and independent bits of shared randomness is both necessary and sufficient for achieving randomized coding capacity. The sufficiency proof is based on deterministic list codes along with a polynomial hashing technique which uses the shared randomness. The converse uses a known approach for binary AVCs and extends it to general 'adversary-weakened' AVCs using a notion of confusable codewords.