<div dir="ltr"><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif">Hi everyone,</span></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif"><br></span></div><div style="">This week will be our final meeting of the quarter. To celebrate, we'll be having a special holiday party version of theory lunch! </div><div style=""><br></div><div style="">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<b> <i>earlier (noon, 12pm)</i></b> and in <b><i>a different location (Cobb 301)</i></b>. The talk will still be held between 1pm - 1.30pm.</div><div style=""><br></div><div style="">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!</div><div style=""><br></div><div style="">Hope to see you all soon,</div><div style="">Antares</div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif;font-size:large"><br></span></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">******************************</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">******************************</span><span style="font-family:Arial,Helvetica,sans-serif;font-size:large">**************************</span><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></b></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></b></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif"><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;color:rgb(49,49,49);word-spacing:1px"><font size="4">Date</font></b><b style="font-family:inherit;font-style:inherit;font-variant-ligatures:inherit;font-variant-caps:inherit;font-size:1.13em;color:rgb(49,49,49);word-spacing:1px">:</b><span style="font-size:1.13em;color:rgb(49,49,49);word-spacing:1px"> </span><span style="color:rgb(49,49,49);word-spacing:1px"><font size="4">December 7, 2022</font></span><br></div><div><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="margin:0px"><div style="color:rgb(32,31,30);margin:0px"><div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Time: </b>12:00pm CT (!!)</font></div><div style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Location: </b>Cobb 301 (!!)</font></div><div dir="auto" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><b><font style="font-size:1.13em"><br></font></b></div><div dir="auto" style="margin:0px;color:rgb(49,49,49);word-spacing:1px"><font size="4"><font face="Calibri, Arial, Helvetica, sans-serif" style="font-weight:bold">Speaker: </font><a href="https://www.andrew.cmu.edu/user/sichaoxu/"><font face="Calibri, Arial, Helvetica, sans-serif" style="">J</font><font face="Arial">eff (Sichao) Xu</font></a></font></div><div dir="auto" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;margin:0px;color:rgb(49,49,49);word-spacing:1px"><font size="4"><br></font></div></div><div style="margin:0px"><span style="color:rgb(49,49,49);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><b>Title: </b>Polynomial-Time Algorithm for Power-Sum Decomposition of Polynomials</font></span></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><b style="color:rgb(49,49,49);font-size:16px;word-spacing:1px"><font style="font-size:1.13em"><br></font></b></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><span style="margin:0px;font-size:16px;color:rgb(49,49,49);word-spacing:1px"><font style="font-size:1.13em"><b>Zoom: </b>[<a href="https://uchicago.zoom.us/j/95507241990?pwd=NTZOemk4RmFoU1JvenpUTUZFcnlPUT09">link</a>]</font></span></div><div style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:15px;margin:0px"><br></div><div style="margin:0px"><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="color:rgb(49,49,49);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:13pt;margin:0px"><b>Abstract:</b></span><span style="color:rgb(32,31,30);font-family:"trebuchet ms",sans-serif;font-size:12pt;margin:0px;word-spacing:0px"> </span></font><font face="arial, sans-serif" size="4">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. <br><br>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 [</font><span style="font-family:arial,sans-serif;font-size:large">GHK15</span><span style="font-family:arial,sans-serif;font-size:large">] yields an algorithm only when $m \leq \widetilde{O}(\sqrt{n})$. On the other hand, the more general recent result of [</span><span style="font-family:arial,sans-serif;font-size:large">GKS20</span><span style="font-family:arial,sans-serif;font-size:large">] 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.</span></div><div dir="auto" style="margin:0px"><font face="arial, sans-serif" size="4"><br>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 <i>exact</i> (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.<br><br>Based on joint work with Mitali Bafna, Jun-Ting Hsieh and Pravesh Kothari. FOCS' 22. Available at <a href="https://arxiv.org/abs/2208.00122">link</a>.</font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><font size="4"><br></font></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">[</span><a href="https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$" rel="noopener noreferrer" title="https://orecchia.net/event/theory-lunch/" target="_blank" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large;margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Theory</span></span></span></span></span> <span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Lunch</span></span></span></span> Webpage</a><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">]</span><br style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">[</span><a href="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$" rel="noopener noreferrer" title="https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America/Chicago" target="_blank" style="font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large;margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Theory</span></span></span></span></span></span></span><span style="margin:0px"> </span><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px"><span style="margin:0px">Lunch</span></span></span></span></span><span style="margin:0px"> </span>Calendar</a><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large">]</span></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="color:rgb(32,31,30);font-family:Calibri,Arial,Helvetica,sans-serif;font-size:large"><br></span></span></font></div><div dir="auto" style="margin:0px"><font style="word-spacing:1px"><span style="margin:0px;word-spacing:0px"><span style="font-size:large">******************************</span><span style="font-size:large">******************************</span><span style="font-size:large">**************************</span></span></font></div></div></div></div></div></div></div></div></div>