Bio
Grigory is an assistant professor at the Computer Science Department at Indiana University, Bloomington. He has been a post-doctoral researcher at Brown University and the University of Pennsylvania. He is broadly interested in theoretical computer science and learning theory, and has worked in the areas of property testing, streaming algorithms, online algorithms, communication complexity and data privacy.
Talk Information
Linear sketching using parities1:45-2:45 PMMEB 3147
AbstractIn the recent years linear sketching has emerged as a powerful tool for approximate computing in settings with limited resources including distributed computation and streaming. It has been used in breakthrough results on graph and matrix processing, dimensionality reduction, etc. Strikingly, linear sketches have been shown to be optimal for dynamic stream processing under fairly mild assumptions.
In this talk I will describe a new study of linear sketching that focuses on understanding the power of linear sketches based on parities (i.e. over
GF_2, the field over two elements, as compared to the previous work that uses real arithmetic). I will illustrate various properties of such sketches using Fourier-analytic methods and tools from communication complexity. In particular, linear sketching over GF_2 turns out to be closely related to Fourier sparsity with respect to Lp-norms. Moreover, it can be shown to be (almost) optimal in streaming and distributed settings for data generated according to the uniform distribution.
Joint work with Sampath Kannan (UPenn) and Elchanan Mossel (MIT).