Algorithmic Problems in Higher-order Fourier Analysis

by Dr. Madhur Tulsiani (Totota Technological Institute at Chicago, USA)

Saturday, January 3, 2015 from 10:00 to 11:00 (Asia/Kolkata)
at AG-66 (Lecture Theatre)

Description

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.