116 Calvin Lab
Generalizations of the FKN Theorem for Boolean functions
Aviad Rubinstein (UC Berkeley)
We consider Boolean functions that are close to a sum of independent functions on mutually exclusive subsets of the variables. We prove that any such function is close to one of those independent functions. We also consider Boolean functions that are close, with respect to any product distribution, to a sum of their variables. We prove that any such function is close to one of the variables. Both our results are independent of the number of variables, but depend on the variance of f. We prove that this dependence is tight. Our results are a generalization of the "FKN Theorem" which proves a similar statement for uniformly distributed Boolean variables.
CLTs for Gaussian chaoses and applications
Anindya De (UC Berkeley)
I will state a CLT for Gaussian chaoses of degree-d and state an application of such a CLT.
Random lifts of small degree
Naman Agarwal (University of Illinois, Urbana-Champaign)
Random lifts of graphs were studied extensively by Linial et al. in a series of papers. In a recent work with Prof. Alexandra Kolla, Vivek Madan we have been studying lifts of small/constant degree (in particular 2 lifts) and have been able to improve known upper bounds on new eigenvalues in some cases. In this talk I would describe lifts, known results and our recent results.
Intersection theorems and the Lovász theta function
Yuval Filmus (University of Toronto)
Erdős, Ko and Rado proved that a k-uniform family of intersecting subsets of [n] has measure at most k/n, as long as k <= n/2. Since then, other results of the same nature have been proved. For example, Ahlswede and Khachatrian extended the former result to t intersecting families, and Ellis, F. and Friedgut extended it to triangle-intersecting families of graphs. Their proof proceeded by computing the theta function of a non-intersection graph. Friedgut used this method to prove the EKR theorem and special cases of the AK theorem, but couldn't prove the complete AK theorem due to an integrality gap. Can sums-of-squares hierarchies come to the rescue?
Measurements of randomness and Interdependence
Ron Blei (University of Connecticut)
Interdependence and randomness can be calibrated by indices based separately on combinatorial measurements, p-variations, and tail-probability estimates. I intend to survey and explain these ideas. No formal proofs will be given. I will speak heuristically, but will try to be precise.