Salim El Rouayheb has started an exciting new initiative inspired by the TCS+ series. TCS+ is a seminar series on theoretical computer science (plus more) given over Google Hangout so that people across the world can attend the talk (and even ask questions). Nobody has to travel anywhere. Salim’s version is for information theory and he’s calling it Shannon’s Channel. If you’re interested in getting announcements you can sign up for the mailing list.
Salim told me about this at Allerton and I meant to plug it here on the blog earlier but then the semester plus excessive travel ate me. He just sent a reminder yesterday that the inimitable Pulkit Grover will be giving a seminar today (Monday) at 1 PM:
Error-correction and suppression in communication and computing: a tradeoff between information and energy dissipation
Abstract: Information naturally tends to dissipate. This dissipation can be slowed down, but this requires increased energy dissipation. Shannon’s capacity theorem can be interpreted as the first word in this information-energy dissipation tradeoff, but it barely scratches the surface. I will begin with a survey of recent results on minimal energy dissipation for reliable information communication. I will discuss how incorporating energy dissipated in transmitter/receiver circuitry as well as in transmission leads to radically different fundamental limits on information-energy interactions than those obtained by Shannon. I’ll also talk about practical applications in short distance wired and wireless communications.
These techniques can also be applied to obtain fundamental limits to information-energy dissipation for reliable computation using unreliable/noisy components (first considered in [von Neumann ’56]). Recent work on strong data-processing inequality points out the fundamental difficulty in noisy computing: information-dissipation across multiple computation steps. We ask the question: what is the minimum energy-dissipation needed to keep information intact (reliability constant) as the computation proceeds? I’ll describe our novel ENCODED strategy (ENcoded COmputation with DEcoders EmbeddeD) for linear computations on noisy substrates, that outperforms uncoded/repetition-based strategies and keeps error-probability bounded below a constant. The key insight is that for computing in noisy environments, repeated error-suppression (that dissipates energy) is essential to keep information from dissipating. Application to emerging devices and circuit design techniques will also be discussed.
Finally, I’ll talk about a high-density noninvasive biopotential sensing problem, which is closely related to the problem of compressing a Markov source distributedly. Here, energy constraints limit the number of sensors. I’ll discuss how a novel “hierarchical” architecture that contains error-accumulation turns out to have a substantially improved energy-information dissipation tradeoff than simply “compressing innovations” (a strategy known to be suboptimal from a work of Kim and Berger).
Unfortunately, I have to teach during that time, otherwise I would totally be there, virtually.