Theory Seminar: Sidharth Jaggi
Tuesday, January 28
Room 142 @ 2:30 pm
Speaker: Sidharth Jaggi, Chinese University of Hong Kong
Title: Shannon-Style Theorems for Adversarial Noise Problems: When Can One Pack (Exponentially) Many Copies of a Given Pattern?
Abstract: Shannon characterized the capacity of general random noise channels to “first order” (fraction of bits reliably transmissible over many channel uses). This work gives the first precise characterization of a “coarser/zeroth-order” question over “harder” channels — specifically, whether a positive communication rate is possible or not over a general channel controlled by an adversary. The difference arises primarily from the difference between “soft” packings (as in Shannon theory) and “hard” packings (as in adversarial problems) in high-dimensional spaces. We answer the problem in great generality: given constraints on the transmitter, on the jammer, and the channel law, we show that a positive communication rate is possible if and only if a certain efficiently computable convex set affiliated with the problem does not completely contain a certain convex set (the set of so-called completely positive distributions) whose geometric properties have been studied in the literature.
Perhaps our main contribution is a lemma of independent interest about long sequences of random variables — the task of generating an arbitrarily long sequence of random variables with all pairs having a joint distribution approximately equaling a pre-specified P(x,x’) is possible if and only if P(x,x’) is a completely positive distribution.
With this framework and lemma in hand we are now able to give precise characterizations for a variety of heretofore open adversarial noise problems, such as general list-decoding/causal/myopic adversary problems.
Joint work with Xishi (Nicholas) Wang, Andrej Bogdanov, Amitalok J. Budkuley.
Bio: Sidharth Jaggi received his B. Tech. from I.I.T. Bombay 2000, his M.S. and Ph.D. degrees from the CalTech in 2001 and 2006 respectively, all in EE. He spent 2006 as a Postdoctoral Associate at LIDS MIT. He joined the Department of Information Engineering at the Chinese University of Hong Kong in 2007, where he is now an Associate Professor. His interests lie at the intersection of network information theory, coding theory, and algorithms. His research group thus (somewhat unwillingly) calls itself the CAN-DO-IT team (Codes, Algorithms, Networks: Design and Optimization for Information Theory). Examples of topics he has dabbled in include network coding, sparse recovery/group-testing, covert communication, and his current obsession is with adversarial channels.
