Speaker: Karl Wimmer Title: Testing Fourier dimensionality and sparsity Abstract: We present a range of new results for testing properties of Boolean functions that are defined in terms of the Fourier spectrum. Broadly speaking, our results show that the property of a Boolean function having a concise Fourier representation (or any sub-property thereof) is locally testable. We first give an efficient algorithm for testing whether the Fourier spectrum of a Boolean function is supported in a low-dimensional subspace of $F_2^n$. (equivalently, for testing whether $f$ is a junta over a small number of parities). We next give an efficient algorithm for testing whether a Boolean function has a sparse Fourier spectrum (small number of nonzero coefficients). We also give an implicit learning algorithm that lets us test any sub-property of Fourier concision. Our technical contributions include new structural results about sparse Boolean functions and new analysis of the pairwise independent hashing of Fourier coefficients introduced by Feldman et. al. This is joint work with Parikshit Gopalan, Ryan O'Donnell, Rocco Servedio, and Amir Shpilka.