Algorithmic Problems in Higher-order Fourier Analysis

Speaker: 

Madhur Tulsiani

Affiliation: 

Toyota Technologica Institute at Chicago
Department of Computer Science
6045 S. Kenwood Ave.
Chicago, Illinois 60637
United States of America

Time: 

Saturday, 3 January 2015, 10:00 to 11:00

Venue: 

Organisers: 

Abstract: 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.