<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body>
<div>
<div>
<div dir="ltr">Please remove me as well thank you!</div>
</div>
<div id="ms-outlook-mobile-signature">
<div><br>
</div>
Get <a href="https://aka.ms/o0ukef">Outlook for iOS</a></div>
</div>
<hr style="display:inline-block;width:98%" tabindex="-1">
<div id="divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" style="font-size:11pt" color="#000000"><b>From:</b> cs <cs-bounces+ameliaspecht=cs.uchicago.edu@mailman.cs.uchicago.edu> on behalf of Deniz Tokmakoglu <denizt@uchicago.edu><br>
<b>Sent:</b> Friday, June 10, 2022 11:50:46 AM<br>
<b>To:</b> techstaff@cs.uchicago.edu <techstaff@cs.uchicago.edu>; cs@cs.uchicago.edu <cs@cs.uchicago.edu>; colloquium@cs.uchicago.edu <colloquium@cs.uchicago.edu><br>
<b>Subject:</b> [CS] Re: Goutham Rajendran Dissertation Defense/Jun 13, 2022</font>
<div> </div>
</div>
<div>
<div>
<div>
<div dir="ltr">Please remove me from dissertation presentation email list. Thanks!</div>
</div>
<div id="x_ms-outlook-mobile-signature">
<div><br>
</div>
<div dir="auto" style="color:rgb(33,33,33); background-color:rgb(255,255,255)">Deniz Tokmakoglu </div>
</div>
</div>
<hr tabindex="-1" style="display:inline-block; width:98%">
<div id="x_divRplyFwdMsg" dir="ltr"><font face="Calibri, sans-serif" color="#000000" style="font-size:11pt"><b>From:</b> cs <cs-bounces+denizt=cs.uchicago.edu@mailman.cs.uchicago.edu> on behalf of Megan Woodward <meganwoodward@uchicago.edu><br>
<b>Sent:</b> Friday, June 10, 2022 9:05:58 AM<br>
<b>To:</b> cs@cs.uchicago.edu <cs@cs.uchicago.edu>; colloquium@cs.uchicago.edu <colloquium@cs.uchicago.edu><br>
<b>Subject:</b> [CS] Goutham Rajendran Dissertation Defense/Jun 13, 2022</font>
<div> </div>
</div>
<div>
<div class="" style="word-wrap:break-word">
<div class="x_x_x_BodyFragment"><font size="2" class=""><span class="" style="font-size:11pt">
<div class="x_x_x_PlainText">This is an announcement of Goutham Rajendran's Dissertation Defense.<br class="">
===============================================<br class="">
Candidate: Goutham Rajendran<br class="">
<br class="">
Date: Monday, June 13, 2022<br class="">
<br class="">
Time: 11 am CST<br class="">
<br class="">
Remote Location: <a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/96784507440?pwd=VlhqVHVJb3p2NStQZWF5aFBXeW1lUT09__;!!BpyFHLRN4TMTrA!9T_YWUkRcGC1HVpMzK-Jd2z9fIk05fILGDuyZ37QshMkz_1HTgIdQ8j4jFEQ9QsQxEqkz0HJa67wsV4rwLYU2DNHa8uGFlw$" class="">https://uchicago.zoom.us/j/96784507440?pwd=VlhqVHVJb3p2NStQZWF5aFBXeW1lUT09</a> Meeting
ID: 967 8450 7440 Passcode: 670915<br class="">
<br class="">
Location: JCL 346<br class="">
<br class="">
Title: Nonlinear Random Matrices and Applications to the Sum of Squares Hierarchy<br class="">
<br class="">
Abstract: We develop new tools in the theory of nonlinear random matrices and apply them to study the performance of the Sum-of-Squares (SoS) hierarchy on average-case problems.<br class="">
<br class="">
The SoS hierarchy is a powerful optimization technique that has achieved tremendous success for various problems in combinatorial optimization, robust statistics and machine learning. It's a family of convex relaxations that lets us smoothly tradeoff running
time for approximation guarantees. In recent works, it's been shown to be extremely useful to recover structure in high dimensional noisy data. It also remains our best approach towards refuting the notorious Unique Games Conjecture.<br class="">
<br class="">
In this work, we analyze the performance of the SoS hierarchy on fundamental problems stemming from statistics, theoretical computer science and statistical physics. In particular, we show subexponential-time SoS lower bounds for the problems of the Sherrington-Kirkpatrick
Hamiltonian, Planted Slightly Denser Subgraph, Tensor Principal Components Analysis and Sparse Principal Components Analysis. These SoS lower bounds involve analyzing large random matrices, wherein lies our main contributions. These results offer strong evidence
for the truth of and insight into the low-degree likelihood ratio hypothesis, an important conjecture that predicts the power of bounded time algorithms for hypothesis testing.<br class="">
<br class="">
We also develop general-purpose tools for analyzing the behavior of random matrices which are functions of independent random variables. Towards this, we build on and generalize the matrix variant of the Efron-Stein inequalities. In particular, our general
theorem on matrix concentration recovers various results that have appeared in the literature. We expect these random matrix theory ideas to have other significant applications.<br class="">
<br class="">
Advisors: Madhur Tulsiani and Aaron Potechin<br class="">
<br class="">
Committee Members: Madhur Tulsiani, Aaron Potechin, and Janos Simon<br class="">
<br class="">
</div>
</span></font></div>
<div class="x_x_x_BodyFragment"><font size="2" class=""><span class="" style="font-size:11pt">
<div class="x_x_x_PlainText"></div>
</span></font></div>
</div>
<div class="" style="word-wrap:break-word">
<div class="x_x_x_BodyFragment"><font size="2" class=""><span class="" style="font-size:11pt">
<div class="x_x_x_PlainText"></div>
<div class="x_x_x_PlainText"><br class="">
</div>
</span></font></div>
</div>
</div>
</div>
</body>
</html>