Information Theory in CS

Harvard FAS

Information Theory originated in the seminal work of Shannon (1948) that aimed to formalize and quantify information. Since the 1990s tools and concepts from Information Theory have played a central role in theoretical computer science. Notable examples include the Parallel Repetition Theorem of Raz (1994), the development of the Information Complexity to understand Communication Complexity (2001). Today Information Theoretic measures and tools influence many aspects of CS theory including…