Colloquium* on *"An almost-linear time deterministic algorithm for expander
decomposition"* given by *Thatchaphol Saranurak*, Toyota Technological
Institute at Chicago. The seminar will take place at *14:00 CEST* (local
time in central Europe), and will be followed by a discussion session. We
would like to invite you to take part in the event including the networking
session. This new event aims to integrate the European algorithmic
community and keep it connected during the times of the pandemic. The
meeting will be held using *Airmeet* platform and to attend please go to
https://www.airmeet.com/e/97c8c5c0-0c70-11eb-98e7-d55d6ecb87dc. You can
find more information about the initiative and the talk on IGAFIT web page:
http://igafit.mimuw.edu.pl/?page_id=483786.
In order to access Airmeet platform, you will need to register, so that
others know who you are. Then before and after the talk, you will be
located inside a Social Lounge, where discussion tables are visible. Most
of the tables can have up to 8 chairs, and you can join a table by clicking
"Take a Seat" button on a table. This way you will be able to talk to
people seating currently at the table. When the session starts you will be
automatically switched to see the stage. You can find more instructions on
how to use Airmeet here:
https://www.airmeet.com/hub/step-by-step-guide-use-airmeet-for-attendees/.
We invite you to take part in the event. Please advertise broadly and bring
your students/postdocs as well.
The details of the talk are given below.
*October 15, 2020, 14:00 CEST*
*Thatchaphol Saranurak*, Toyota Technological Institute at Chicago
Title: *An almost-linear time deterministic algorithm for expander
decomposition*
Abstract: Expander decomposition is a powerful tool in many areas on graph
algorithms (e.g. approximation algorithm, dynamic algorithm, distributed
algorithm, property testing, and sketching). We give a deterministic
algorithm for finding this decomposition in almost-linear time. Previous
algorithms are either randomized or take quadratic time. As a consequence,
we resolve a major open problem if there is a deterministic dynamic
connectivity algorithm with n^{0.4999} worst-case update time by giving an
algorithm with n^{o(1)} worst-case update time. The result also implies
almost-linear-time deterministic algorithms for approximate max flow,
electric flow, and Laplacian solvers.
Joint work with Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, and
Richard Peng.
Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Adi Rosén
Eva Rotenberg
Piotr Sankowski
Christian Sohler
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
