Please note the unusual time(!) for the next talk on the IGAFIT Algorithmic
Colloquium *this Thursday:*
*February 11, 2021, 16:00 CEST *(not the usual 14:00 time)
*Jason Li*, Carnegie Mellon University
Title: *Deterministic Mincut in Almost-Linear Time*
Abstract: We present a deterministic (global) mincut algorithm for
weighted, undirected graphs that runs in m^{1+o(1)} time, answering an open
question of Karger from the 1990s. To obtain our result, we de-randomize
the construction of the skeleton graph in Karger's near-linear time mincut
algorithm, which is its only randomized component. In particular, we
partially de-randomize the well-known Benczur-Karger graph sparsification
technique by random sampling, which we accomplish by the method of
pessimistic estimators. Our main technical component is designing an
efficient pessimistic estimator to capture the cuts of a graph, which
involves harnessing the expander decomposition framework introduced in
recent work by Goranci et al. (SODA 2021). As a side-effect, we obtain a
structural representation of all approximate mincuts in a graph, which may
have future applications.
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/e9359160-6a97-11eb-b0c9-6bf245ad3423.
You can find more information about 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
the "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.
Organization Committee:
Nikhil Bansal
Artur Czumaj
Andreas Feldmann
Danupon Nanongkai
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
