Appears in collection : 2016 - T1 - WS2 - Fundamental inequalities and lower bounds theme

Fano's inequality can be viewed as capturing a deep interplay between information and computation. It links storage, reconstruction and transmission in one inequality, generalizing arguments as simple as the pigeonhole principle, and leading us to inequalities by Assouad and LeCam. In this presentation I'll explain how Fano's inequality gets used to reason about data structures, statistics and inference.