- Diversity, Equity, and Inclusion
- Research News
- Department Life
- Oral History of Cornell CS
- CS 40th Anniversary Booklet
- ABC Book for Computer Science at Cornell by David Gries
- Department Timeline
- Job Postings
- Ithaca Info
- Internal info
- Graduation Information
- Cornell Tech Colloquium
- Student Colloquium
- Fall 2023 Colloquium
- Conway-Walker Lecture Series
- Salton 2023 Lecture Series
- Seminars / Lectures
- Big Red Hacks
- Cornell University High School Programming Contests 2023
- Game Design Initiative
- CSMore: The Rising Sophomore Summer Program in Computer Science
- Explore CS Research
- ACSU Research Night
- Cornell Junior Theorists' Workshop
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 with Andrea Montanari and Mark Sellke.
Bio: Ahmed El Alaoui is an assistant professor at the Department of Statistics and Data Sciences at Cornell University, since January 2021. Before joining Cornell, he was a postdoctoral researcher from 2018 to 2020 at Stanford University, hosted by Andrea Montanari. Ahmed received his PhD in 2018 in Electrical Engineering and Computer Sciences from UC Berkeley, under the supervision of Michael Jordan. His research interests revolve around high-dimensional statistics and probability theory, statistical physics, algorithms, and problems where these areas meet.