Schedule
This talk is a mathematical primer for the rest of the
workshop. I define the basic notions that form the foundations of
higher-order Fourier analysis over finite fields, such as bias, Gowers
norm and polynomial rank. I will discuss the interrelationships between
these notions, regularity lemmas and show proofs of mini-results to
illustrate the theorems.
Higher-order Fourier analysis is a strong tool in the study of
analytic averages involving linear structures. One examines such
averages by replacing the involved functions by their Higher-order
Fourier expansion and reducing the problem to studying averages
involving bounded degree polynomials. However for this representation to
be useful, one often needs nice distributional/pseudorandomness
properties of the involved polynomials such as approximate orthogonality
or almost independence.
We will talk about regularity of polynomials which was
introduced by Green-Tao and Kauffman-Lovett in order to provide such
approximate orthogonalities. In most applications, however, one requires
stronger regularity properties of the polynomials. We will overview the
proof of such a strong near-orthogonality over arbitrary systems of
linear forms, and show as an application that this can be used to settle
a conjecture of Gowers and Wolf regarding the true complexity of
systems of linear forms.
The talk is based on a joint work with Hamed Hatami and Shachar Lovett.
12:35-14:00 Lunch break
Decomposition theorems proved by Gowers and Wolf provide an
appropriate notion of "Fourier transform" for higher-order Fourier
analysis. We will discuss some questions and techniques that arise from
trying to develop polynomial time algorithms for computing these
decompositions.
The original proofs for these theorems were non-constructive
and used the Hahn-Banach theorem. We will discuss constructive proofs
based on boosting which reduce the problem of computing these
decompositions to a certain kind of weak decoding for codes beyond the
list-decoding radius. We will also describe some special cases for which
such decodings are known to be possible, and the techniques which
achieve these.
Based on joint works with Arnab Bhattacharyya, Eli Ben-Sasson, Pooya Hatami, Noga Ron-Zewi and Julia Wolf.
Property testing aims for constant-query algorithms that
distinguish objects satisfying a predetermined property from objects
that are “far” from satisfying it. Along with the development of the
higher order Fourier analysis, there has been rapid progress in testing
affine-invariant properties of functions over a finite field, including
low-degree polynomials, and finally a characterization of
affine-invariant properties that are testable with a constant number of
queries was achieved. In this talk, we survey these results.
15:30-16:00 Coffee break
Let S and T be two dense subsets of Gn, where G is the special linear group SL(2,p) for a prime p congruent to 3 modulo 4. If you sample uniformly a tuple (s1,...,sn) from S and a tuple (t1,...,tn) from T then their interleaved product s1.t1.s2.t2...sn.tn is equal to any fixed g in G with probability (1 + |G|-Ω(n))/|G|.
Equivalently, the communication complexity of distinguishing tuples whose interleaved product is equal to g from those whose product is equal to a different g' is Ω(n log |G|),
even if the protocol is randomized and only achieves a small advantage
over random guessing. This result is tight and improves on the Ω(n) bound that follows by reduction from the inner product function.
Gowers (2007) and later Babai, Nikolov, and Pyber proved that if S, T, and U are dense subsets of a simple, non-abelian group G, then STU = g with probability (1/|G|)(1 + o(1)). For the special case of G = SL(2,p), this also follows from our result. Unlike previous proofs, ours does not rely on representation theory.
Joint work with Timothy Gowers.
for a finite field 
is defined by n-variate degree-d polynomials over 
; and Gopalan established it for d = 2
and all fields. In a recent work with Lovett, we prove the conjecture
for all constant prime fields and all constant degrees. The proof relies
on several new ingredients, including higher-order Fourier analysis.