CanaDAM 2019
SFU Harbour Centre, May 29 - 31, 2019

Additive combinatorics I
Org: Hamed Hatami (McGill University)

HAMED HATAMI, McGill University
Influences of coalitions over arbitrary product distributions  [PDF]

The seminal result of Kahn, Kalai and Linial shows that a coalition of $o(n)$ players can bias the outcome of any Boolean function $\{0,1\}^n \to \{0,1\}$ with respect to the uniform measure. We extend their result to arbitrary product measures on $\{0,1\}^n$, by combining their argument with a completely different argument that handles very biased coordinates.

This is based on a joint work with Yuval Filmus, Lianna Hambardzumyan, Pooya Hatami, and David Zuckerman.

SHACHAR LOVETT, University of California San Diego
The sunflower conjecture - new perspectives  [PDF]

The Erdos-Rado sunflower conjecture is one of the tantalizing open problems in combinatorics. I will describe how it relates to topics studied in theoretical computer science, such as randomness extractors and DNF compression. In particular, how improved constructions for these objects implies improved bounds for the sunflower conjecture.

Based on joint works with Xin Li, Noam Solomon and Jiapeng Zhang.

COSMIN POHOATA, Caltech University
Upper bounds for sets of points with prescribed pairwise distances  [PDF]

A subset $S$ of a metric space $M$ is called an $s$-distance set if the pairs of points in $S$ determine $s$ distinct positive distances $d_{1},\ldots,d_{s}$, which are all realized. There are many well-known problems in extremal combinatorics which ask about or reduce to upper bounding the size of $S$, under various additional hypotheses. In the talk, we will discuss the case when $M$ is $\mathbb{R}^{d}$ (with the usual Euclidean distance metric), $\left\{0,1\right\}^{n}$ (with the usual Hamming metric), and connections between these and the recent Croot-Lev-Pach method from additive combinatorics.

AVISHAY TAL, Stanford University
Fourier Tails of Boolean Functions and Their Applications  [PDF]

The discrete Fourier expansion is a widely used tool in Boolean functions analysis, representing a Boolean function as a multilinear polynomial. Several well-studied classes of Boolean functions (e.g., DNF formulae) have the property that they can be very well-approximated by the low-degree part of their Fourier expansion. We study this phenomenon and draw equivalences to the behavior of the functions under random restrictions.

Furthermore, we show that being well-approximated by low-degree polynomials implies being approximated by sparse polynomials (not necessarily low-degree). This latter property applies to a wider class of Boolean functions and has important applications to pseudorandomness.