[Theory] [Theory Lunch] Jeff (Sichao) Xu, Wednesday 12/7 12:00pm-1:30pm, Cobb 301

[Antares Chen]

Hi everyone,

This week will be our final meeting of the quarter. To celebrate, we'll be
having a special holiday party version of theory lunch!

Along with our regularly planned lunch, we'll be serving some additional
snacks, confections, and drinks. To accommodate the additional food, we'll
be starting* earlier (noon, 12pm)* and in *a different location (Cobb 301)*.
The talk will still be held between 1pm - 1.30pm.

Additionally, Jeff is visiting Hyde Park between Wednesday and Friday this
week. He is generally interested in Sum-of-Squares, average-case problems
and would love to meet folks around the department. If you're interested in
chatting please reach out!

Hope to see you all soon,
Antares

************************************************************
**************************

*Date**:* December 7, 2022
*Time: *12:00pm CT (!!)
*Location: *Cobb 301 (!!)

Speaker: Jeff (Sichao) Xu <https://www.andrew.cmu.edu/user/sichaoxu/>

*Title: *Polynomial-Time Algorithm for Power-Sum Decomposition of
Polynomials

*Zoom: *[link
<https://uchicago.zoom.us/j/95507241990?pwd=NTZOemk4RmFoU1JvenpUTUZFcnlPUT09>
]

*Abstract:* We give efficient algorithms for finding power-sum
decomposition of an input polynomial $P(x)= \sum_{i\leq m} p_i(x)^d$ with
component $p_i$s. The case of linear $p_i$s is equivalent to the
well-studied tensor decomposition problem while the quadratic case occurs
naturally in studying identifiability of non-spherical Gaussian mixtures
from low-order moments.

Unlike tensor decomposition, both the unique identifiability and algorithms
for this problem are not well-understood. For the simplest setting of
quadratic $p_i$s and $d=3$, prior work of [GHK15] yields an algorithm only
when $m \leq \widetilde{O}(\sqrt{n})$. On the other hand, the more general
recent result of [GKS20] builds an algebraic approach to handle any
$m=n^{O(1)}$ components but only when $d$ is large enough (while yielding
no bounds for $d=3$ or even $d=100$) and only handles an inverse
exponential noise.

Our results obtain a substantial quantitative improvement on both the prior
works above even in the base case of $d=3$ and quadratic $p_i$s.
Specifically, our algorithm succeeds in decomposing a sum of $m \sim
\widetilde{O}(n)$ generic quadratic $p_i$s for $d=3$ and more generally the
$d$th power-sum of $m \sim n^{2d/15}$ generic degree-$K$ polynomials for
any $K \geq 2$. Our algorithm relies only on basic numerical linear
algebraic primitives, is *exact* (i.e., obtain arbitrarily tiny error up to
numerical precision), and handles an inverse polynomial noise when the
$p_i$s have random Gaussian coefficients.

Based on joint work with Mitali Bafna, Jun-Ting Hsieh and Pravesh Kothari.
FOCS' 22. Available at link <https://arxiv.org/abs/2208.00122>.

[Theory Lunch Webpage
<https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$>
]
[Theory Lunch Calendar
<https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAsww4XtIRnQ$>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221204/09ad9cf1/attachment.html>