Theory Lunch Seminar

  • Gates Hillman Centers
  • ASA Conference Room 6115
  • Senior
  • Departments of Computer Science and Mathematical Sciences
  • Carnegie Mellon University

Escaping small sets on the Boolean cube and other domains

If we perform a random walk starting from a subset of the Boolean hypercube, how long does the walk have to be before we expect to end outside the set? In this talk I will answer this question by introducing hypercontractivity and logarithmic Sobolev inequalities on the Boolean hypercube, which are tools in showing that all "small" sets on the hypercube have large boundary size. These tools additionally imply many classical results about functions on the Boolean hypercube.

Next, I will describe our work extending hypercontractivity and log-Sobolev inequalities to non-product domains. We consider "multislices", which are subsets of [L]^n having exactly k_i coordinates equal to i for all i in [L], and k_1 + k_2 + ... + k_L = n. Consider the Markov chain induced by random transpositions of coordinates. We prove an upper bound on the inverse log-Sobolev constant on this chain, and from this we derive some consequences for small set expansion and isoperimetry on the multislice.

Based on joint work with Yuval Filmus and Ryan O'Donnell.

Vist CMU Youtube Theory Channel for post-event videos.

For More Information, Please Contact: