EE Systems Seminar
ABSTRACT The question of when communication is possible in an adversarial jamming context is intimately connected to the question of high-dimensional packings -- for instance, communication over a binary-input binary-output channel where the adversary can flip up to pn bits is equivalent to designing packings of pn-radius Hamming balls in n-dimensional Hamming space.
We consider a fairly general class of adversarial channels, and:
* Show that each adversarial channel has a bijection with a certain "confusability polytope" embedded in the simplex of all distributions of joint-types of pairs of inputs to the channel, and
* Precisely characterize when a positive rate is possible (i.e., exponential-size packings are possible). Sufficiency is characterized in terms of codes where each pair of codewords has joint-type given by a "completely positive distribution" outside the confusability polytope.
Necessity follows by a Ramsey theoretic argument showing that each large code must have a sufficiently large subcode where each pair of codewords has roughly the same type-class, followed by a generalized Plotkin-type argument, and a Fourier-analytic analysis of a certain game.
Joint ongoing work with Andrej Bogdanov, Nicholas Wang, and Amitalok Budkuley.
BIO Sidharth Jaggi received his Bachelor of Technology degree from the Indian Institute of Technology in 2000, and his Master of Science and Ph.D. degrees from the California institute of Technology in 2001 and 2006 respectively, all in electrical engineering. He was awarded the Caltech Division of Engineering Fellowship 2001-'02, and the Microsoft Research Fellowship for the years 2002-'04. He interned at Microsoft Research, (Redmond, WA, USA) in the summers of 2002-'03 and engaged in research on network coding. He spent 2006 as a Postdoctoral Associate at the Laboratory of Information and Decision Systems at the Massachusetts Institute of Technology. He joined the Department of Information Engineering, the Chinese University of Hong Kong in 2007.