Linear Sketching for Functions over the Boolean Hypercube

Originally introduced as a tool for dimensionality reduction and streaming algorithms, linear sketching has recently emerged as a powerful tool for algorithm design in a wide variety of domains: numerical linear algebra, graph algorithms, sampling, signal processing, distributed algorithms, etc. This has made linear sketching an indispensable tool in algorithmist's toolkit that is covered in depth in modern big data processing courses.

In this talk I will describe a new study of linear sketching which focuses on understanding the power of linear sketches based on parities (i.e. over F_2, the field of two elements, as compared to the previous work that uses real arithmetic). The talk will be self-contained and won't assume prior knowledge of linear sketching. I will illustrate various properties of such sketches using Fourier-analytic methods and tools from communication complexity. In particular, linear sketching over F_2 turns out to be closely related to Fourier sparsity with respect to Lp-norms. Moreover, it can be shown to be optimal in streaming and distributed settings for data generated according to the uniform distribution.

Joint work with Sampath Kannan (UPenn), Elchanan Mossel (MIT) and Swagato Sanyal (NUS), CCC 2018
Grigory Yaroslavtsev is an assistant professor of Computer Science at Indiana University and the founding director of the Center for Algorithms and Machine Learning at IU. Prior to that he was 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 2014 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. His work is supported by NSF CRII Award and Facebook Faculty Research Award.