### Monday, April 10th, 2017

What structure/randomness dichotomies can be found across families of infinite structures? How precisely can we pinpoint the interactions of randomness and freedom vs structure and control inside a structure? Model theory has long investigated these questions. It turns out that model theoretic theorems about infinite objects can have strong consequences for finite objects. The talk will expand on these questions and some motivating consequences from the speaker's work (joint with S. Shelah), including characterization of the existence of irregular pairs in Szemeredi's regularity lemma and proofs of instances of Erdos-Hajnal.

### Tuesday, April 11th, 2017

We discuss a variant of the density and energy increment arguments that we call an "entropy decrement method", which can be used to locate a scale in which two relevant random variables share very little mutual information, and thus behave somewhat like independent random variables. We were able to use this method to obtain a new correlation estimate for multiplicative functions, which in turn was used to establish the Erdos discrepancy conjecture that any sequence taking values in {-1,+1} had unbounded sums on homogeneous arithmetic progressions.

### Wednesday, April 12th, 2017

This is part of our ongoing efforts to understand high-dimensional combinatorial objects. These include simplicial complexes (a 1-dimensional simpicial complex is a graph), high-dimensional permutations (e.g., a 2-dimensional permutation is synonymous with a Latin square), hypertrees and more. For every type of combinatorial object that we wish to study it is crucial to understand their typical behavior. Namely, to understand the properties of random objects of the type that we study. In this talk I describe recent work with my student Maya Dotan which allows us to efficiently generate random one-factorizations. I will also mention ongoing work with my student Michael Simkin on random generation of Latin squares. In addition I will speak about joint work with Zur Luria on low-discrepancy high-dimensional permutations.

### Thursday, April 13th, 2017

Positional games are perfect information games between two players with no chance moves. As such, they do not seem to allow much room for randomness and random considerations. Yet, as convincingly shown by intensive research in the last decades, randomness is omnipresent in positional games and manifests itself in a variety of ways, including:

- probabilistic (looking) winning criteria;

- guessing the threshold bias of biased games; - winning using random play;

- playing on random boards;

- introducing randomness into game rules.

In this survey talk I will discuss and illustrate the rich interplay between positional games and randomness, concentrating mostly on Maker-Breaker games. Essentially no prior experience with positional games will be assumed.

Let f:F_2^n --> {0,1} be a function and suppose F_2^n x F_2^n is partitioned into k sets A_i x B_i such that f is constant on each sumset A_i + B_i. We show this implies a partitioning of F_2^n to quasipoly(k) affine subspaces such that f is constant on each. In other words, up to polynomial factors, deterministic communication complexity and parity decision tree complexity of f are equal. This relies on a novel technique of entropy decrement combined with Sanders' Bogolyubov-Ruzsa lemma.

Joint work with Hamed Hatami and Shachar Lovett.

A random subset with density alpha of an n-dimensional vector space over a finite field on p elements likely has about an alpha^3 fraction of the three-term arithmetic progressions with each nonzero common difference. Note that, for a subset of density alpha, the density of three-term arithmetic progressions can be much smaller than alpha^3. However, Green proved that for each epsilon>0 there is n_p(epsilon) such that if the dimension n of the vector space is at least n_p(epsilon), then there always exists a nonzero common difference d with three-term arithmetic progression density at least alpha^3-epsilon, what we expect from the random bound. The proof uses the arithmetic regularity lemma and gives a bound on n_p(epsilon) which is an exponential tower with height polynomial in 1/epsilon.

We provide a construction which shows that n_p(epsilon) is at least a tower with height logarithmic in 1/epsilon when epsilon is small, and prove a matching upper bound up to constant factor in the tower height. This gives the first natural application of a regularity lemma where the tower type bound is really necessary. Tight bounds are also obtained for other ranges of epsilon (in terms of the density alpha).

This is joint work with Jacob Fox and Yufei Zhao.

Locally decodable codes (LDCs) are error correcting codes that allow for decoding of a single message bit using a small number of queries to a corrupted encoding. In this work, we give a new characterization of LDCs using distributions over smooth Boolean functions whose expectation is hard to approximate (in~$L_\infty$~norm) with a small number of samples. We give several candidates for such distributions coming from finite field incidence geometry and from hypergraph (non)expanders. We also prove a useful lemma showing that (smooth) LDCs which are only required to work on average over a random message and a random message index can be turned into true LDCs at the cost of only constant factors in the parameters.