In 1988 Kahn, Kalai, and Linial published their landmark paper in which they proved a lower bound on the maximal influence of variables on a Boolean function. Their use of Fourier analysis to solve the question, and especially their introduction of a hypercontractive inequality (due to Bonami, Beckner, and Gross), has shaped the field of study of Boolean functions and has had a great influence on combinatorics and theoretical computer science. 

In this paper I survey how my own work has been influenced by their approach, via a collection of various problems that I have approached throughout the years.

KKL’s influence on me

Ehud Friedgut

Abstract