Discrete Math Seminar: Igor Shinkar

We study the computational hardness 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-hard 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 any graph G, let H be a random subgraph of G obtained by deleting the edges of G independently with probability 0.5. We show that if $\chi(G)$ is large, then $\chi(H)$ is also large with high probability. This means that the chromatic number of any graph is ``robust'' to random edge deletions.

Joint work with Huck Bennett and Daniel Reichman.