## Schedule

##### 11:00-11:50 **Background on higher-order Fourier analysis (Arnab Bhattacharyya, IISc )**

##### 11:55-12:35 **Regularity of polynomials and linear forms (Pooya Hatami, U. Chicago)**

##### 12:35-14:00 **Lunch break**

##### 14:00-14:40 **Algorithmic higher-order Fourier analysis (Madhur Tulsiani, TTIC)**

##### 14:50-15:30 **Applications to algebraic property testing (Yuichi Yoshida, NII)**

##### 15:30-16:00 **Coffee break**

##### 16:00-16:40 **Applications to coding theory (Abhishek Bhowmick, UT Austin)**

*n*-variate degree-*d* polynomials over .
As far as we know, the list decoding radius of Reed- Muller codes can
be as large as the minimal distance of the code. This is known in a
number of cases: The Goldreich-Levin theorem and its extensions
established it for *d = 1* (Hadamard codes); Gopalan, Klivans and Zuckerman established it for the binary field ; 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.

##### 16:50-17:30 **Interleaved products in special linear groups: mixing and communication complexity (Emanuele Viola, Northeastern)**

*S* and *T* be two dense subsets of *G ^{n}*, 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

*(s*from

_{1},...,s_{n})*S*and a tuple

*(t*from

_{1},...,t_{n})*T*then their interleaved product

*s*is equal to any fixed

_{1}.t_{1}.s_{2}.t_{2}...s_{n}.t_{n}*g*in

*G*with probability

*(1 + |G|*.

^{-Ω(n)})/|G|*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.

*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.