Tata Institute of Fundamental Research
Algorithmic Problems in Higher-order Fourier Analysis
STCS Seminar
Speaker:
Madhur Tulsiani (Toyota Technologica Institute at Chicago
Department of Computer Science
6045 S. Kenwood Ave.
Chicago, Illinois 60637
United States of America)
Organiser:
Arkadev Chattopadhyay
Date:
Saturday, 3 Jan 2015, 10:00 to 11:00
Venue:
AG-66 (Lecture Theatre)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Madhur Tulsiani (Toyota Technologica Institute at Chicago Department of Computer Science 6045 S. Kenwood Ave. Chicago, Illinois 60637 United States of America) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Saturday, 3 Jan 2015, 10:00 to 11:00 |
| Venue: | AG-66 (Lecture Theatre) |
(Scan to add to calendar)
Abstract:
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.
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.