Logo

Mathematical Sciences Research Institute

Home » MSRI/Pseudorandomness seminar: Local central limit theorems for combinatorial problems

Seminar

MSRI/Pseudorandomness seminar: Local central limit theorems for combinatorial problems April 27, 2017 (03:45 PM PDT - 04:45 PM PDT)
Parent Program:
Location: MSRI: Simons Auditorium
Speaker(s) Shachar Lovett (University of California, San Diego)
Description No Description
Video
No Video Uploaded
Abstract/Media

Consider the following combinatorial problem. A t-(n,k,lambda) block design is a family of k-sets of [n], such that any t-set of [n] is contained in exactly lambda of the k-sets in the family. An (l; n,k,t) large set is a partition of all k-sets to t-(n,k,lambda) block designs (where necessarily lambda={n-t choose k-t}/l).

For which values of n,k,t,l to these objects exist? The known explicit constructions cover very few settings. So, it makes sense to study probabilistic constructions. A uniform partition of all the k-sets of [n] to l parts is very unlikely to produce an (l; n,k,t) large set. But is the probability of success zero, or merely tiny and positive (which suffices for proving existence)?

I will describe a general technique to analyze such problems, based on harmonic analysis and local central limit theorems. Surprisingly, the techniques to control the Fourier tail rely on concepts arising in coding theory.

https://arxiv.org/abs/1302.4295

https://eccc.weizmann.ac.il/report/2017/070/



Based on joint works with Greg Kuperberg, Ron Peled, Sankeerth Rao and Alex Vardy.

No Notes/Supplements Uploaded No Video Files Uploaded