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 12/10: Tselil Schramm on Sum-of-Squares Algorithms

Dan Michael Stubbs dstubbs at
Wed Dec 9 12:30:36 PST 2015

Tomorrow, Thursday December 10, we will have the last theory lunch of the quarter and year.  The speaker is Tselil Schramm from Berkeley.  Food around 12:15, talk begins at 12:30.

Be there!



Overcomplete Tensor Decomposition: Speeding up Sum-of-Squares Algorithms

Recently, there has been some success in using the sum-of-squares
hierarchy to solve classical problems in machine learning. However,
the sum-of-squares algorithms are very slow, making them impractical
for the machine learning setting. In this talk I will show that ideas
from sum-of-squares rounding schemes can be used to obtain fast,
spectral algorithms. I will focus on the problem of decomposing an
overcomplete low-rank random tensor into rank-1 components, showing
that ideas from the quasi-polynomial sum-of-squares algorithm can be
adapted to achieve similar performance in subquadratic time.

Based on joint work with Sam Hopkins, Jonathan Shi and David Steurer.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list