**Speaker**: Yi Li (李翼), Nanyang Technological University

**Date**: Tue, Jul 10, 2018

**Time**: 15:30 - 16:30

**Venue**: Middle Meeting Room

**Title**: Estimating the Schatten norms of matrices in streaming model

**Abstract**:

A popular data stream model in theoretical computer science is the turnstile streaming model, in which there is an underlying vector which is initialized to 0 and receives incremental updates to its coordinates. The goal is to compute some function of the vector at the end of the stream without essentially storing the entire vector. A well-studied problem in the literature is approximating the ell_p norms of the vector; in this talk I shall study the analogous problem of estimating matrix Schatten norms. I intend to present a systematic summary of latest results on the space complexity of estimating the Schatten p-norms of an n x n matrix in the turnstile streaming model. Both kinds of space complexities, bit complexity and sketching dimension, are considered.