IISER Mohali, Knowledge city, Sector 81, SAS Nagar, Manauli PO 140306

Fourier-Walsh coefficients, noise sensitivity and randomized algorithms

Prof. D. Yogeshwaran (ISI, Bangalore)

Zoom Link

Location Online
Abstract:
This talk will mainly be about some inequalities for functions on the hypercube / Rademacher space (i.e., {-1,+1}^n equipped with the uniform measure). In a celebrated work, Kahn, Kalai and Linial (1988) improved the Poincare' inequality (also known as Efron-Stein inequality in this case) for such functions by introducing tools from harmonic analysis. Building upon this, Benjamini, Kalai and Schramm (1999), introduced the concept of noise sensitivity for Boolean functions (i.e., {0,1}-valued functions) and showed it to be equivalent to the vanishing of its `low-frequency' energy spectrum. Later Schramm and Steif (2010) proved an inequality for the Fourier-Walsh coefficients of a function in terms of a randomized algorithm that determines the function, thereby allowing one to quantitatively estimate the energy spectrum of a function by constructing good randomized algorithms. This inequality was extremely useful in proving quantitative noise sensitivity in many applications. The Schramm-Steif inequality also improved upon the classical Poincare' inequality in a different direction compared to KKL (1988). I shall try to review these results, ideas and some related developments in the study of functions on the Rademacher space.

Towards the end of the talk, I shall preview a recent joint work with Giovanni Peccati (Luxembourg) and Guenter Last (Karlsruhe) where we develop analogues of these inequalities for functions of certain random locally-finite point sets, namely the Poisson point process.

Most of the talk should be accessible to those with a knowledge of basic probability and some analysis.

Please check the following google site for more information on the seminars.
https://sites.google.com/view/apsiisermohali/home

Meeting ID: 943 7403 6747
Passcode: 518065
Go to top