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
Tue Oct 10 15:22:40 PDT 2017

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

As usual, the talk starts at 12:30pm. See you all!



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

This is joint work with Pravesh Kothari.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list