[Colloquium] U of C - CS Theory Seminar - Alex Wein, April 18, 2023

[Jose J Fragoso]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS



Alex Wein, PhD
University of California, Davis


[A person smiling for the camera  Description automatically generated with medium confidence]


Tuesday, April 18, 2023 at 3:30pm
Kent Chemical Laboratory, Room 120 (New Room)



Title: Is Planted Coloring Easier than Planted Clique?


Abstract:  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).

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.

Our computational hardness results are based on the low-degree polynomial model of computation or reductions from planted clique.

Based on joint work with Pravesh Kothari, Santosh Vempala, and Jeff Xu, available at https://arxiv.org/abs/2303.00252<https://urldefense.com/v3/__https:/arxiv.org/abs/2303.00252__;!!BpyFHLRN4TMTrA!4W4oPKgYCgEftJz5JywxJukkxW6WmfbQ0-og5uHjDr-xPVnMVXNp2kQbAqXgTGV5YfRKSDAEvKlHcPNmh6HFySg$>


Bio:  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.






Host: Aaron Potechin











-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230414/f656c9a4/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 8621 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20230414/f656c9a4/attachment-0001.jpg>