Pulkit Grover, UC Berkeley
Wednesday Oct 27th. 2010
Abstract: Shannon theory tells us how to communicate explicit sources across explicit channels. However, systems in nature (e.g. bacteria), society (e.g. dancing), and economics (e.g. market signaling) are rife with examples where neither the source nor channel is explicit, and actions, not words, are used to “speak.” Can we design cyber-physical systems and control policies inspired by these examples? Unfortunately, toy problems of implicit communication appear to be harder than those of explicit communication — even the point-to-point implicit communication problem, the Witsenhausen counterexample, remains unsolved despite research effort spanning 40 years.
I will first present our main technical contribution: a provably approximately-optimal solution to the Witsenhausen counterexample (and its vector extensions) using tools from information theory. We first address an asymptotic version of the problem, and then pull results back to finite lengths using a “sphere-packing” philosophy. This characterizes the optimal costs for the (scalar) Witsenhausen counterexample to within a factor of 8, and are the first results of their kind for the long-standing problem.
Our results raise questions which have not be explored earlier. For instance, what happens when there is choice between implicit and explicit communication? I will show that nature may have it right: ignoring implicit communication for its explicit counterpart can lead to unbounded losses. What if both options are available? We will derive strategies that use implicit and explicit communication in a synergistic manner, and outperform the best known strategies by an unbounded factor.
Pulkit Grover (BS ’03, IIT Kanpur, MS ’05, IIT Kanpur) is a postdoc at Wireless Foundations, Electrical Engineering and Computer Sciences, UC Berkeley, where he will soon graduate from. His research interests are in information theory, control and low-power circuits. He is particularly interested in developing a theory of information for decentralized control, and in low-power circuits for wireless communications and bioelectronics.
Host: Rahul Jain, rahul.jain [at] usc
Back to CommNetS Seminar Page