BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//hacksw/handcal//NONSGML v1.0//EN
BEGIN:VEVENT
UID:node-12061@prod.cs.cornell.edu
DTSTAMP:20220411T194500Z
DTSTART:20220411T194500Z
DTEND:20220411T203500Z
SUMMARY:Computing Extremal Cuts in Locally Treelike Graphs
DESCRIPTION:Ahmed El Alaoui, Cornell University. Computing Extremal Cuts in Locally Treelike Graphs (via Zoom)Abstract: We consider the problem of efficiently computing a near maximum cut or a near minimum bisection of a regular graph of large girth. We develop an iterative local algorithm which, when given a k-regular graph of girth 2L, produces a cut with the following two extremal properties when k and L are large:(1) The achieved cut value is approximately optimal among all L-local algorithms. (2) This value approximately matches the true 'ground state' value on random k-regular graphs. As a consequence, random regular graphs have approximately minimum max-cut value, and maximum min-bisection value among all locally-treelike regular graphs of the same degree. This can be seen as a combinatorial version of the near-Ramanujan property of random regular graphs. This is based on a joint work...https://prod.cs.cornell.edu/content/computing-extremal-cuts-locally-treelike-graphs
LOCATION:Gates 114, streaming via Zoom
END:VEVENT
END:VCALENDAR