A semigroup approach to Talagrand-type isoperimetric inequalities

Abstract

This thesis primarily concerns isoperimetric inequalities in analysis of Boolean functions. Isoperimetry, as a classic geometric topic studying the quantitative relation between the perimeter and volume of a set, is closely related to the influence and sensitivity properties when applied to Boolean functions. More specifically, a Boolean function, as a function mapping each binary vector in the hypercube to a binary value, always serves as an indicator of a subset of the hypercube. The influence and sensitivity of a Boolean function then characterize the size of the boundary of the subset it indicates. Early examples of isoperimetric inequalities in analysis of Boolean functions are provided by the Poincar\'{e} inequality and the KKL inequality.

Our research work focuses on a special type of isoperimetric inequalities which stems from Talagrand’s discrete analogue of the Gaussian isoperimetric inequality, referred to as the Talagrand-type isoperimetric inequalities. In an epitomizing work by Elden and Gross, the authors validated a Talagrand's conjecture for the tenability of an isoperimetric inequality of this type, and established a general result that unifies several celebrated historical isoperimetric inequalities including KKL inequality and Talagrand’s isoperimetric inequality. This was achieved through a novel method of conducting stochastic analysis on the random walk on the hypercube.

Inspired by the aforementioned work, we develop a semigroup approach towards Talagrand-type isoperimetric inequalities, which further unifies a series of historical results in analysis of Boolean functions and can be extended to functions in very general settings. We first perform a semigroup analysis to obtain variance decay inequalities, which serve as the intermediate between canonical functional inequalities and Talagrand-type isoperimetric inequalities. Then we establish a general implication relation from variance decay to Talagrand-type isoperimetric inequalities through conducting stochastic analysis on the Markov process associated to the noise semigroup on the hypercube. Our approach provides a valuable framework for generating such isoperimetric inequalities and understanding the root of their formation.