Spectral sparsity plays an important role in many different areas of computer science and signal processing, including data compression, error-correcting codes, learning theory, communication complexity, property testing, and parity decision tree complexity. In particular, sparsity allows one to design Sparse Fourier Transforms which can be dramatically more efficient than the regular Fast Fourier Transforms. However, performance of such algorithms is conditioned on the sparsity assumption. Much less is known about verifying this assumption efficiently. In this talk I will describe new algorithms for testing whether a given function over the Boolean hypercube is close to being sparse in the Fourier spectrum.
Joint work with Andrew Arnold, Arturs Backurs, Eric Blais and Krzysztof Onak
Speaker's bio: Grigory Yaroslavtsev is a postdoctoral fellow at the Warren Center for Network and Data Sciences at the University of Pennsylvania. He was previously a Postdoctoral Fellow in Mathematics at Brown University, ICERM. He received his Ph.D. in Theoretical Computer Science in 2013 from Pennsylvania State University and an M.Sc. in Applied Mathematics and Physics from the Academic University of the Russian Academy of Sciences in 2010. Grigory works on efficient algorithms for sparsification, summarization and testing properties of large data, including approximation, parallel and online algorithms, learning theory and property testing, communication and information complexity and private data release.