UVictoria Dynamics and Probability Seminar: Sajin Koroth

Lifting theorems have played a key role in many recent breakthrough results in diverse areas of theoretical cs and mathematics via simple yet profound connections between these areas and communication complexity. A typical lifting theorem translates the query complexity (a very simple model of computation) of a Boolean function to the communication complexity (a more powerful model) of an associated function obtained by a central operation of Boolean functions known as block-composition by composing with another function known as inner function. Most lifting theorems work for any Boolean function f and depend upon the pseudo-random properties of the inner function g known as the gadget. The main parameter of efficiency in lifting theorems is the input size of the inner function g. Obtaining lifting theorems for constant-sized gadgets would give us breakthrough results and a nearly complete understanding of lifting phenomena; current techniques are far from achieving this goal. The main barrier is the existence of “nice” pseudo-random properties for well-known gadgets when their input length is relatively small compared to the outer function. Recent results have shown that understanding the pseudo-random properties is inherently connected to interesting questions in combinatorics (like the sunflower lemma) and in Boolean function analysis. In this talk, we will go through a high level overview of lifting theorems and the necessary condition that enable lifting phenomenon. We will also see some applications of lifting theorems in diverse areas of theoretical cs and mathematics, achieved via surprising yet simple connections. We will also go over recent advances in understanding the pseudo-random properties that drive the lifting phenomena and important barriers and open problems related to this.