On Percolation and NP-Hardness
Igor Shinkar (Simon Fraser University)
Abstract: We study the computational complexity of problems whose inputs are obtained by applying random noise to worst-case instances. For an appropriate notion of noise we show that a number of classical NP-complete problems on graphs remain essentially as hard on the noisy instances as they are in the worst-case.
Focusing on the Graph Coloring problem, we establish the following result: Given a graph $G$, consider a random subgraph of $G$ obtained by deleting the edges of $G$ independently with probability $0.5$. We show that if the chromatic number of $G$ is large, then with high probability the chromatic number of the random subgraph remains large. That is the chromatic number of any graph is ``robust'' to random edge deletions.
Joint work with Huck Bennett and Daniel Reichman.
computer science theorycombinatorics
Audience: researchers in the discipline
LA Combinatorics and Complexity Seminar
Series comments: Password is on the seminar page. www.math.ucla.edu/~pak/seminars/CCSem-Fall-2020.htm
| Organizers: | Igor Pak*, Greta Panova |
| *contact for this listing |