Los Angeles Combinatorics and Complexity Seminar: On Percolation and NP-Hardness

Tuesday, October 27, 2020 at 10:15am to 10:45am

This is a past event.
Virtual Event

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.

Dial-In Information

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.

Event Type

Lecture / Talk / Workshop

Add this to your calendar

Recent Activity