Tuesday, October 27, 2020 at 10:15am to 10:45am
Igor Shinkar, Simon Fraser University, BC, Canada
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.
Zoom Meeting: https://ucla.zoom.us/j/96564290758
Meeting ID: 965 6429 0758
Passcode: Please see your email for the passcode to join via Zoom
Warning: You must be registered under your name to be admitted.