## Discrete Math Seminar: Igor Shinkar

• Date: 11/22/2016
• Time: 16:00
Lecturer(s):
Igor Shinkar: UC Berkeley
Location:

University of British Columbia

Topic:

On Percolation and NP-Hardness

Description:

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.