FOURIER: Fourier Analysis in Theoretical Computer Science

09:00-10:00 A Robust Sparse Fourier Transform in the Continuous Setting (Eric Price)

In recent years, a number of works have studied methods for computing the complex Fourier transform in sublinear time if the output is sparse. Most of these have focused on the discrete setting, even though in many applications the input signal is continuous and naive discretization significantly worsens the sparsity level. We present an algorithm for robustly computing sparse Fourier transforms in the continuous setting. We contribute:

• A natural definition of the goal: an L2 guarantee in terms of the time domain over the sampled duration. Previous works measured error in frequency domain, which is impossible to achieve robustly.
• An algorithm achieving this guarantee with sample and time complexity linear in the sparsity and logarithmic in the signal-to-noise ratio and the frequency resolution.

10:00-10:30 Tea/coffee/snack break

10:30-11:30 The Fourier Entropy Influence Conjecture (Satya Lokam)

We will introduce and motivate the Fourier Entropy Influence conjecture made by Friedgut and Kalai (1996). The conjecture has been proved for some special classes of functions. Some weaker versions of the conjecture are also known to be true. We will survey the state of the art in progress toward resolving this conjecture.

11:30-12:30 Higher-order Fourier analysis and an application (Arnab Bhattacharyya)

This talk introduces the basic notions that form the foundations of higher-order Fourier analysis over finite fields, such as bias, Gowers norm and polynomial rank, and also the relationships between them. These tools are then used to obtain a lower bound on the length of locally correctable affine-invariant codes. Our lower bound is in fact achieved by the recent lifted codes of Guo, Kopparty and Sudan.

Joint work with Sivakanth Gopi.

12:30-14:00 Lunch break

14:00-15:00 Algorithmic higher-order Fourier analysis (Madhur Tulsiani)

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.

Based on joint works with Arnab Bhattacharyya, Eli Ben-Sasson, Pooya Hatami, Noga Ron-Zewi and Julia Wolf.

15:00-15:30 Tea/coffee/snack break

15:30-16:30 Open problem session