Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch Spring Edition 3/31: Esty Kelman

Junyao Zhao junyaoz at stanford.edu
Tue Mar 29 10:07:43 PDT 2022


Hi everyone,

Hope you had a nice spring break!

The spring edition of theory lunch will begin this Thursday at noon in the Engineering Quad<https://www.google.com/maps/place/Science+%26+Engineering+Quad+Courtyard/@37.4284882,-122.1765394,17z/data=!3m1!4b1!4m5!3m4!1s0x808fbb8ce58bcc27:0x677c06a883bb7bb7!8m2!3d37.428484!4d-122.1743507>. We'll start with some socializing, followed by a talk at 12:30pm. Esty will tell us about Analysis of Boolean functions: KKL Theorem via Random Restrictions and Log-Sobolev Inequality

Abstract: A Boolean function over the n-dimensional binary hypercube is a function f of the form f:{0,1}^n->{0,1}. The KKL Theorem [STOC'88], a fundamental result in the field that is named after Kahn, Kalai, and Linial, states the following:

Every Boolean function f on n variables has a single variable with a non-trivial influence on the value of f. The theorem was proved using Fourier analysis and other novel techniques that are still widely used today. A particular ingredient in the proof is the hypercontractive inequality, which became a key theorem in many proofs in this field. As hypercontractive inequality is sometimes considered a bit counter-intuitive, researchers try to avoid using it and develop alternative tools that yield the same and even stronger results.

We establish an alternative proof technique for the KKL Theorem, as well as for other related results, avoiding the use of hypercontractive inequality. Instead, we apply a suitable random restriction on the function, i.e., choosing a random set of variables and fixing them to a random value. Then, we follow by applying the Log-Sobolev inequality. (A particular case of The Log-Sobolev inequality is the edge isoperimetric inequality, which states that each small subset of vertices of the n-dimensional binary hypercube has many outgoing edges that connect it to other vertices of the graph.).
Our proofs might serve as an alternative, uniform exposition to these theorems, and the techniques might be useful to obtain more results.

In this talk, we will prove a special case of the KKL Theorem using our new approach and demonstrate how to apply the random restriction and the edge isoperimetric inequality.

Based on a joint work with Subhash Khot, Guy Kindler, Dor Minzer and Muli Safra.

By the way, we have some slots available for talks (4/21, 5/5, 5/19, and 6/2). If you want to share some cool math with the group, please let me know.

Wishing you a great start of the spring quarter!

Cheers,
Junyao

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220329/b7a66aa9/attachment-0003.html>


More information about the theory-seminar mailing list