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

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.

Audience: Graduate  Undergraduate  Post-Docs 

remind we with google calendar

 

March 2024

SU MO TU WE TH FR SA
25 26 27 28 29 1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31 1 2 3 4 5 6
Submit an Event