BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Igor Shinkar (Simon Fraser University)
DTSTART:20201027T171500Z
DTEND:20201027T174500Z
DTSTAMP:20260423T010528Z
UID:LA-CoCo/15
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/LA-CoCo/15/"
 >On Percolation and NP-Hardness</a>\nby Igor Shinkar (Simon Fraser Univers
 ity) as part of LA Combinatorics and Complexity Seminar\n\n\nAbstract\nWe 
 study the computational complexity of problems whose inputs are obtained b
 y applying random noise to worst-case instances. For an appropriate notion
  of noise we show that a number of classical <b>NP</b>-complete problems o
 n graphs remain essentially as hard on the noisy instances as they are in 
 the worst-case.\n\nFocusing on the <i>Graph Coloring problem</i>\, we esta
 blish the following result: Given a graph $G$\, consider a random subgraph
  of $G$ obtained by deleting the edges of $G$ independently with probabili
 ty $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 larg
 e. That is the chromatic number of any graph is ``robust'' to random edge 
 deletions.\n\nJoint work with Huck Bennett and Daniel Reichman.\n
LOCATION:https://researchseminars.org/talk/LA-CoCo/15/
END:VEVENT
END:VCALENDAR