<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<!--[if !mso]><style>v\:* {behavior:url(#default#VML);}
o\:* {behavior:url(#default#VML);}
w\:* {behavior:url(#default#VML);}
.shape {behavior:url(#default#VML);}
</style><![endif]--><style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:0 0 0 0 0 0 0 0 0 0;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
font-size:10.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
span.apple-converted-space
{mso-style-name:apple-converted-space;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;
mso-ligatures:none;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple" style="word-wrap:break-word">
<div class="WordSection1">
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"> <o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102"> </span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">UNIVERSITY OF CHICAGO</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">COMPUTER SCIENCE DEPARTMENT</span></i><o:p></o:p></p>
<p class="MsoNormal"><i><span style="font-size:12.0pt;font-family:Helvetica;color:#8B0102">PRESENTS</span></i><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:12.0pt;font-family:Helvetica">Alex Wein, PhD</span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica">University of California, Davis</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p class="MsoNormal"><img width="183" height="244" style="width:1.9062in;height:2.5416in" id="Picture_x0020_3" src="cid:image001.jpg@01D966D1.773A2E80" alt="A person smiling for the camera
Description automatically generated with medium confidence"><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;font-family:Helvetica;color:black"> </span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black">Tuesday, </span>
</b><b><span style="font-size:11.0pt">April 18<span style="color:black">, 202</span>3<span style="color:black"> at 3:30pm</span></span></b><o:p></o:p></p>
<p class="MsoNormal"><b><span style="font-size:11.0pt;color:black;background:yellow">Kent Chemical Laboratory, Room 120 (New Room)</span></b><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt;color:black"> </span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p style="margin:0in"><b><i><span style="font-size:12.0pt">Title:</span></i></b><span style="font-size:12.0pt">
<span style="color:#212121">Is Planted Coloring Easier than Planted Clique?</span></span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p style="margin:0in"><b><i><span style="font-size:12.0pt">Abstract:</span></i></b><b><span style="font-size:12.0pt">
</span></b><span style="font-size:12.0pt"> <span style="color:#212121">I will discuss algorithms and computational complexity for various average-case problems related to q-colorability in the random graph G(n,1/2): recovery of a planted q-coloring, testing
the number of colors in a planted q-coloring, and algorithmically refuting q-colorability of G(n,1/2).<br>
<br>
By taking the complement of the graph, the planted q-coloring model is analogous to the classical planted clique model but with many planted cliques. Here our conclusion is that adding more cliques makes the detection problem easier but not the recovery problem.<br>
<br>
Our computational hardness results are based on the low-degree polynomial model of computation or reductions from planted clique.<br>
<br>
Based on joint work with Pravesh Kothari, Santosh Vempala, and Jeff Xu, available at<span class="apple-converted-space"> </span></span></span><a href="https://urldefense.com/v3/__https:/arxiv.org/abs/2303.00252__;!!BpyFHLRN4TMTrA!4W4oPKgYCgEftJz5JywxJukkxW6WmfbQ0-og5uHjDr-xPVnMVXNp2kQbAqXgTGV5YfRKSDAEvKlHcPNmh6HFySg$" title="https://urldefense.com/v3/__https://arxiv.org/abs/2303.00252__;!!BpyFHLRN4TMTrA!4W4oPKgYCgEftJz5JywxJukkxW6WmfbQ0-og5uHjDr-xPVnMVXNp2kQbAqXgTGV5YfRKSDAEvKlHcPNmh6HFySg$"><span style="font-size:12.0pt;color:#0078D7">https://arxiv.org/abs/2303.00252</span></a><o:p></o:p></p>
<p> <o:p></o:p></p>
<p class="MsoNormal"><b><i><span style="font-size:12.0pt">Bio:</span></i></b><span style="font-size:12.0pt">
<span style="color:#212121">Alex Wein received his PhD from MIT in 2018 supervised by Ankur Moitra. He is now an Assistant Professor in the Department of Mathematics at UC Davis. His research spans theoretical computer science, statistics, probability, and
data science, with an emphasis on understanding the computational complexity of high-dimensional statistical inference. He is a recipient of the Charles W and Jennifer C Johnson Prize from MIT, and the 2023 Sloan Research Fellowship.</span></span><o:p></o:p></p>
<p class="MsoNormal"><span style="font-size:11.0pt"> </span><o:p></o:p></p>
<p> <o:p></o:p></p>
<p><span style="color:black"> </span><o:p></o:p></p>
<p style="margin-bottom:12.0pt"><b><span style="font-size:12.0pt;font-family:Helvetica;color:black">Host:<span class="apple-converted-space"> Aaron Potechin</span></span></b><br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
<o:p></o:p></p>
</div>
</body>
</html>