What's it about?

Fourier analysis is a key tool in mathematics, and it has found many applications in theoretical computer science. The goal of this workshop is to present some new directions and problems related to Fourier analysis that have arisen in CS applications.

The first two talks will be about Fourier analysis in the classical sense. Eric Price (UT, Austin) will speak about a robust, efficient algorithm to compute the Fourier transform for continuous input signals that are sparse in the frequency domain. Satya Lokam (Microsoft Research, India) will describe progress on an intriguing and important 20-year old conjecture relating the Fourier spectrum of Boolean functions with their average sensitivity.

The second two talks will focus on higher-order Fourier analysis where one extends the notion of characters to low-degree polynomial phases. This area of study originated in the seminal work of Gowers on Szemeredi's theorem and has been extensively developed in the last few years resulting in some striking applications to computer science. Arnab Bhattacharyya (IISc) will describe the foundations of the area in the context of a new result on locally correctable codes. Madhur Tulsiani (TTIC) will speak about algorithmic problems in higher-order Fourier analysis and applications to coding theory.

We conclude with an open problem session.

When and where is it?

It will be held right after FSTTCS 2015 on December 19, 2015 in Room 117, CSA, IISc.

Who is it for?

The workshop is intended for a general TCS audience, including (of course!) students interested in learning about the area.