### DIMACS Theoretical Computer Science Seminar

Title: Streaming Symmetric Norms via Measure Concentration

Speaker: **Lin F. Yang**, Johns Hopkins University

Date: Wednesday, February 10, 2016 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

We characterize the streaming space complexity of every symmetric norm * l* (a norm on Rⁿ invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of * l*. Specifically, we provide upper and lower bounds on the space complexity of approximating the norm of the stream, where both bounds depend on the median and maximum of * l*(x) when x is drawn uniformly from the * l*₂ unit sphere. The same quantity governs many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem. The family of symmetric norms contains several well-studied norms, such as all * l*p norms, and indeed we provide a new explanation for the disparity in space complexity between *p*≤ 2 and *p>2*. In addition, we apply our general results to easily derive bounds for several norms were not studied before in the streaming model, including for example the top-* k* norm and the * k*-support norm, which was recently shown to be effective for machine learning tasks.

See: http://www.cs.rutgers.edu/~allender/theory-spring16.html