Unlike the other colloquium presentations, this talk will concern the role of feedback in source coding, namely the number of transmitted bits required when a sender conveys information to a receiver over a noiseless channel, and the transmission savings afforded when the receiver can provide the sender with feedback.
We will review basic results in the area, showing for example that communication with no feedback may require exponentially more bits than the minimum necessary, and that one feedback message is always nearly optimal.
Results will be demonstrated via examples and experiments on popular program downloads. The talk will be self contained.
Based on joint work with Abbas El Gamal, Moni Naor, Peter Shor, and Krishna Viswanathan, and on results by other researchers.