<html><head><meta http-equiv="content-type" content="text/html; charset=us-ascii"></head><body dir="auto"><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 12pt; font-family: Helvetica;">Alex Wein, PhD</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;">University of California, Davis</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><img width="183" height="244" id="Picture_x0020_3" src="cid:78312CC8-88DD-40F0-A5B7-EEF1FBD3B499" alt="image001.jpg" _mf_state="1" title="null" style="width: 1.9062in; height: 2.5416in;"><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;"> </span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; font-family: Helvetica;"> </span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;"><span dir="ltr" style="text-decoration: underline;">Tuesday, </span></span></b><b><span style="font-size: 11pt;"><span dir="ltr" style="text-decoration: underline;">April 18</span><span dir="ltr" style="text-decoration: underline;">, 202</span><span dir="ltr" style="text-decoration: underline;">3</span><span dir="ltr" style="text-decoration: underline;"> at 3:30pm</span></span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; background-color: yellow;">Kent Chemical Laboratory, Room 120 (New Room)</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p style="-webkit-text-size-adjust: auto; margin: 0in;"><b><i><span style="font-size: 12pt;">Title:</span></i></b><span style="font-size: 12pt;"> <span style="color: rgb(33, 33, 33);">Is Planted Coloring Easier than Planted Clique?</span></span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p style="-webkit-text-size-adjust: auto; margin: 0in;"><b><i><span style="font-size: 12pt;">Abstract:</span></i></b><b><span style="font-size: 12pt;"> </span></b><span style="font-size: 12pt;"> <span style="color: rgb(33, 33, 33);">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$" style="color: blue;"><span style="font-size: 12pt; color: rgb(0, 120, 215);">https://arxiv.org/abs/2303.00252</span></a></p><div dir="ltr"></div></body></html>