A Picture is Worth a Thousand Words, Its Essence is Checked in Three

Madhu Sudan (Harvard University)

When journalistic photography first emerged, the phrase used in our title conveyed a message about the power of visual imagery. Today, when images, speech and video are digitized, Information Theory puts on a
spin on the statement: A single picture (roughly 100K bytes) is worth, mathematically, ten thousand words (1 word = 10 bytes).

Science's early skirmishes with Information focused on (i) compressing it and (ii) securing data integrity against the wear-and-tear of the elements. More recently, Computer Science expanded our scope of inquiry to ensure the (iii) integrity of proofs and computation, not just data, and do so (iv) succinctly, reading only 3 bits of information(!).

In this talk we will tour the history of data digitization, starting with the definition of Information, methods for error-correction, and the dominance of algebraic methods. Then we'll turn attention to modern considerations such as "probabilistically checkable proofs"? (PCPs) which are amazingly efficient methods of protecting data and its analysis from errors.