[Colloquium] REMINDER: 3/15 Research at TTIC: Thatchaphol Saranurak, TTIC

[Alicia McClarin]

*When:*      Friday, March 15th. Refreshments at noon. Talk begins at 12:20
.

*Where:*    TTIC, 6045 S Kenwood Avenue, 5th Floor, Room 526

*Who: *      Thatchaphol Saranurak, TTIC

*Title: *      Expander decomposition: fast algorithms and applications

*Abstract:*  An (\epsilon,\phi)-expander decomposition of a graph G=(V,E)
with m edges is a partition of vertices into clusters such that (1) each
cluster induces subgraph with conductance at least \phi, and (2) the number
of inter-cluster edges is at most \epsilon*m. This decomposition has a wide
range of applications including approximation algorithms for the unique
game, fast algorithms for flow and cut problems, and dynamic graph
algorithms.

I will describe a new algorithm for constructing (~O(\phi),\phi)-expander
decomposition in ~O(m/\phi) time. This is the first nearly linear time
algorithm when \phi is at least 1/polylog(m), which is the case in most
practical settings and theoretical applications. Previous results either
take \Omega(m^{1+o(1)}) time, or attain nearly linear time but with a
weaker expansion guarantee where each output cluster is guaranteed to be
contained inside some unknown expander. This talk is based on joint work
with Di Wang [Saranurak Wang SODA'19].

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

*Research at TTIC Seminar Series*

TTIC is hosting a weekly seminar series presenting the research currently
underway at the Institute. Every week a different TTIC faculty member will
present their research.  The lectures are intended both for students
seeking research topics and adviser, and for the general TTIC and
University of Chicago communities interested in hearing what their
colleagues are up to.

To receive announcements about the seminar series, please subscribe to the
mailing list: https://groups.google.com/a/ttic.edu/group/talks/subscribe

Speaker details can be found at: http://www.ttic.edu/tticseminar.php.

For additional questions, please contact Nathan Srebro at nati at ttic.edu
<mcallester at ttic.edu>

-- 
*Alicia McClarin*
*Toyota Technological Institute at Chicago*
*6045 S. Kenwood Ave., **Office 510*
*Chicago, IL 60637*
*773-702-5370*
*www.ttic.edu* <http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20190314/d35f2be6/attachment-0001.html>