Lunch In Theory This Thursday (12:00 PM, 02/18, GCS 302c)
3 views
Skip to first unread message
Devansh Gupta
Feb 18, 2026, 1:16:10 PM (5 days ago) Feb 18
to usc-t...@googlegroups.com, CS Theory Group, USC Theory Group, jacketsj
Hi all,
Please join us for Lunch in Theory this Thursday, 02/18 at 12:00 PM in GCS 302c. This week we have a guest speaker, Jack Spalding Jamieson presenting an exciting talk on graph partitioning. Please find the title and abstract attached.
Reminder: Please bring your own lunch, as lunch will not be provided.
Best,
Devansh
Title: Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
Abstract: Graph partitioning is the study of breaking a graph into smaller parts. One key structure from this area with widespread use in algorithms is the concept of a "small balanced vertex separator". Although small balanced vertex separators are known to exist for a number of graph classes (planar graphs, genus-g graphs, forbidden-minor graphs, geometric graphs, and more), the corresponding algorithms to compute these separators are often intractable. In this work, we show that an unspecialized polynomial-time algorithm called "reweighted spectral partitioning" can be used to obtain near-optimal small balanced vertex separators for many graph classes, even though the algorithm itself does not make use of any specialized information about these graph classes.
Abstract: Graph partitioning is the study of breaking a graph into smaller parts. One key structure from this area with widespread use in algorithms is the concept of a "small balanced vertex separator". Although small balanced vertex separators are known to exist for a number of graph classes (planar graphs, genus-g graphs, forbidden-minor graphs, geometric graphs, and more), the corresponding algorithms to compute these separators are often intractable. In this work, we show that an unspecialized polynomial-time algorithm called "reweighted spectral partitioning" can be used to obtain near-optimal small balanced vertex separators for many graph classes, even though the algorithm itself does not make use of any specialized information about these graph classes.
Devansh Gupta
Feb 19, 2026, 3:03:28 PM (4 days ago) Feb 19
to usc-t...@googlegroups.com, CS Theory Group, USC Theory Group, jacketsj
Reply all
Reply to author
Forward
0 new messages