Please Note: This seminar will be given in person.
|
Probability seminar series
Alexander
Wein Room: M3 3127 |
Is Planted Coloring Easier than Planted Clique?
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