Monday, November 7th, 2016 4pm-5pm Burnside 1205
UC Berkeley
On Percolation and NP-Hardness

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.

Fall 2016 Schedule