Please note the Colloquium talk will be held in B11 Kimball Hall and via Zoom

Data compression is a key concept in computer science, relevant in contexts such as data storage and transmission, learnability of patterns from data, and complexity theory. In particular, in complexity theory, a Boolean function is considered hard if its truth table cannot be compressed by Boolean circuits. 

But how difficult is it to estimate the inherent compressibility of a string?
This question is the focus of a thriving research program in "meta-complexity", ie., the complexity of complexity (since incompressibility can be considered as a measure of the complexity of a string). I will discuss various recent results connecting this question to fundamental results and directions in areas such as learning theory, cryptography, complexity lower bounds, and Gödel-type incompleteness phenomena in computer science. 

Rahul Santhanam is a Professor of Computer Science at Oxford and a Tutorial Fellow at Magdalen College. He obtained a Ph.D. in Computer Science from the University of Chicago in 2005, working under the supervision of Prof. Lance Fortnow and Prof. Janos Simon. After postdoctoral stints at Simon Fraser University and the University of Toronto, he joined the University of Edinburgh as a Lecturer in Computer Science in 2008. He was promoted to Reader in 2013 and moved to Oxford in 2016. In 2013, he was awarded the ERC Consolidator Grant ALUnif on "Algorithms and Lower Bounds: A Unified Approach", which he held from March 2014 until August 2019.