Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] [theory-lunch] Jacob Steinhardt on Certifying 2->q Norm

Hongyang Zhang hongyang at
Thu Oct 12 10:16:21 PDT 2017

Reminder this is today at noon.

On Tue, 10 Oct 2017 at 3:22 PM Hongyang Zhang <hongyang at>

> Hi Everyone
> This *thursday 12:00pm to 1:00pm, at Gates 463A*, Jacob Steinhardt will
> tell us about "Certifying 2-q Norms with Sum-of-Squares". See below for the
> abstract.
> As usual, the talk starts at 12:30pm. See you all!
> -hongyang
> ------------------------------------------------------------
> Title: Certifying 2->q Norm with Sum-of-Squares
> Abstract: Approximating the 2->q norm is a natural geometric problem which
> is closely related to the unique games conjecture. BBHKSZ12 show that the
> sum-of-squares (SOS) hierarchy is able to approximate the 2->q norm well on
> points sampled from product distributions on the hypercube, but the general
> performance of SOS on 2->q norm is not well-understood. I will show that
> for distributions satisfying the *Poincare inequality*, m rounds of
> sum-of-squares are sufficient to approximate the 2->m norm for all even m
> >= 2. This substantially extends the result of BBHKSZ12. As applications we
> present improved algorithms for clustering and robust mean estimation. The
> proof exploits recent advances in geometric probability by Adamczak and
> Wolff.
> This is joint work with Pravesh Kothari.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list