[Theory] [Theory Lunch] Antares Chen, Wednesday 11/30 12:30pm-1:30pm, JCL 298

[Antares Chen]

************************************************************
**************************

*Date**:* November 16, 2022
*Time: *12:30pm CT
*Location: *JCL 298

Speaker: Antares Chen <https://antaresc.github.io/>

*Title: *Spectral Graph Theory Without a Spectrum II: Partitioning
Hypergraphs via Network Flows

*Zoom: *[link
<https://uchicago.zoom.us/j/99432914621?pwd=VEpkcnhySEx2dXpjNVF2TmNvV095Zz09>
]

*Abstract:* Last time, we discussed a non-linear and non-differentiable
Laplacian operator for hypergraphs in which aspects of spectral graph
theory still generalize to the hypergraph setting. Building on these tools,
we discuss a primal-dual approximation algorithm for a specific class of
hypergraph partitioning problems called "minimum ratio-cut". To do this, we
construct a family of local, convex relaxations of the minimum ratio-cut
problem, and compose dual solutions using "cut-matching games" to certify
lower bounds on the minimum ratio-cut objective. This approach leads to the
first O(log n)-approximation for minimum ratio-cut that runs in
almost-linear time.

Joint work with Konstantinos Ameranis, Lorenzo Orecchia, and Erasmo Tani.

[Theory Lunch Webpage
<https://urldefense.com/v3/__https://orecchia.net/event/theory-lunch/__;!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAswwp_F5nRs$>
]
[Theory Lunch Calendar
<https://urldefense.com/v3/__https://calendar.google.com/calendar/u/0/embed?src=c_osgf1c1qemdras8mu7l7pdhjrs@group.calendar.google.com&ctz=America*Chicago__;Lw!!BpyFHLRN4TMTrA!pwdRh9yLA-IBD6NCNvREJGd9Nj5jtC6_N-AowF6HSwIQeb1FPAmu0L_tAsww4XtIRnQ$>
]

************************************************************
**************************
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20221129/689a9f16/attachment.html>