Follow us on twitter and facebook.
(To subscribe to the IGAFIT Algorithmic Colloquium mailing list with announcements send an email to igafitcolloquiumrequest@mimuw.edu.pl with subject SUBSCRIBE.)
IGAFIT Algorithmic Colloquium #11
April 8, 2021  
FineGrained Complexity of Optimization Problems  
Karl Bringmann, Saarland University  
Abstract: Finegrained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on conjectures such as the Strong Exponential Time Hypothesis. This enables the design of “bestpossible” algorithms, where the running time of the algorithm matches a conditional lower bound. This talk surveys the developments of finegrained complexity on classic optimization problems such as Subset Sum. In particular, since recently we know a bestpossible algorithm for solving Subset Sum in pseudopolynomial time. We survey this result and the subsequent developments on approximation algorithms, output sensitive algorithms, and pseudopolynomial algorithms under different parameters. We also discuss extensions to other optimization problems such as Knapsack and Partition, scheduling, and integer linear programming. 
(to be posted soon) see the video: colloquium #11 
IGAFIT Algorithmic Colloquium #10
March 25, 2021 
Beyond WorstCase Analysis 
Tim Roughgarden, Columbia University 
Abstract: One of the primary goals of the mathematical analysis of algorithms is to provide guidance about which algorithm is the “best” for solving a given computational problem. Worstcase analysis summarizes the performance profile of an algorithm by its worst performance on any input of a given size, implicitly advocating for the algorithm with the bestpossible worstcase performance. Strong worstcase guarantees are the holy grail of algorithm design, providing an applicationagnostic certification of an algorithm’s robustly good performance. However, for many fundamental problems and performance measures, such guarantees are impossible and a more nuanced analysis approach is called for. Research in “beyond worstcase analysis” develops alternatives to worstcase analysis, with applications ranging from clustering to linear programming to neural network training. This talk will highlight a mix of classic results, recent developments, and open questions in the area. 
see the video: colloquium #10 
IGAFIT Algorithmic Colloquium #9
March 11, 2021 
Graph Clustering Algorithms: Theoretical Insights For Practice 
Vincent CohenAddad, Google Zürich 
Abstract: A classic problem in machine learning and data analysis is to partition the vertices of a graph into very dense subgraphs with low expansion. In practice, the most popular approaches often rely on local search or greedy algorithms; not only for the ease of implementation, their scalability and their efficiency, but also because of the accuracy of these methods on many real world graphs. Even though we can’t prove that these algorithms have good performance guarantees in the worstcase, can we understand what make them so successful in practice? We review two popular objective functions — modularity and correlation clustering — and shed some light on the innerworkings of a popular heuristic (the socalled Louvain algorithm) by providing a “beyond worstcase” analysis. We then describe some key ideas to design graph clustering algorithms in massively parallel environments so as to optimize the above objective in only a constant number of rounds. 
see the video: colloquium #9 
IGAFIT Algorithmic Colloquium #8
February 11, 2021 
Deterministic Mincut in AlmostLinear Time 
Jason Li, Carnegie Mellon University 
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 derandomize the construction of the skeleton graph in Karger’s nearlinear time mincut algorithm, which is its only randomized component. In particular, we partially derandomize the wellknown BenczurKarger 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 sideeffect, we obtain a structural representation of all approximate mincuts in a graph, which may have future applications. 
IGAFIT Algorithmic Colloquium #7
January 28, 2021 
Paths, cycles and beyond 
Fedor V. Fomin, University of Bergen 
I will speak about old and new parameterized algorithms for finding long paths and cycles in graphs. In particular, we discuss problems of finding paths and cycles whose lengths are beyond some “trivial” bounds. 
IGAFIT Algorithmic Colloquium #6
December 10, 2020 
Circulation control for faster minimum cost flow in unitcapacity graphs 
Adrian Vladu, Université de Paris 
In recent years, continuous optimization primitives have become an essential component in the algorithmist’s toolkit. Among other developments, this has led to tremendous progress on the quest for developing fast graph algorithms. In this talk I will give an overview of the techniques based on interior point methods, which have been instrumental to obtaining a set of faster algorithms for fundamental graph problems, which include an m^{4/3+o(1)} log W time algorithm for solving the minimum cost flow problem in graphs with unit capacity. For sparse graphs, our algorithm improves over the best known running time for this problem and, by wellknown reductions, also implies improved running times for the shortest path problem with negative weights, minimum cost bipartite bmatching when b_{1} = O(m), and recovers the running time of the recent unit capacity maximum flow algorithm due to LiuSidford. Based on https://arxiv.org/abs/2003.04863 
IGAFIT Algorithmic Colloquium #5
November 26, 2020 
Fully online matching 
Zhiyi Huang, University of Hong Kong 
Motivated by applications such as ride sharing, we introduce a fully online model of maximum cardinality matching in which all vertices arrive and depart online. On the arrival of a vertex, its edges to previouslyarrived vertices are revealed. The vertex can be matched anytime before its departure, which is after all its neighbors’ arrivals. This fully online matching model generalizes the online bipartite matching model which only considers bipartite graphs and assumes one side of the vertices to be offline. We generalize the Ranking and WaterFilling algorithms to fully online matching and its fractional relaxation respectively. The former is 0.521competitive in general graphs, and 0.567competitive in bipartite graphs, and the latter is 0.585 competitive in both cases. Further, we prove that fully online matching is strictly harder than online bipartite matching, because no online algorithm can be 0.6317 <(11/e)competitive in fully online matching even for bipartite graphs. Finally, we introduce new algorithms that are strictly better than Ranking and WaterFilling in fully online matching. 
see the video: Colloquium #5 
IGAFIT Algorithmic Colloquium #4
November 12, 2020 
New lower and upper bounds for quantile summary algorithms 
Graham Cormode, University of Warwick 
Finding the median, or more generally quantiles, is a core problem in data analysis. The question has been heavily studied in streaming and related models of computation, for over four decades. In this talk I will present some recent advances:

IGAFIT Algorithmic Colloquium #3
October 29, 2020 
A (slightly) improved approximation algorithm for metric TSP 
Nathan Klein, University of Washington 
In this talk, he describes recent work in which he obtains a 3/2ε approximation algorithm for metric TSP, for some ε>10^{36}. This slightly improves over the classical 3/2 approximation algorithm due to Christofides [1976] and Serdyukov [1978]. The talk focuses on giving an overview of the key ideas involved. This is joint work with Anna Karlin and Shayan Oveis Gharan. 
IGAFIT Algorithmic Colloquium #2
October 15, 2020 
An almostlinear time deterministic algorithm for expander decomposition 
Thatchaphol Saranurak, Toyota Technological Institute at Chicago 
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 almostlinear 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} worstcase update time by giving an algorithm with n^{o(1)} worstcase update time. The result also implies almostlineartime 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. 
IGAFIT Algorithmic Colloquium #1
October 1, 2020 
An improved approximation algorithm for ATSP 
Vera Traub, ETH Zürich 
In a recent breakthrough, Svensson, Tarnawski, and Végh gave the first constantfactor approximation algorithm for the asymmetric traveling salesman problem (ATSP). In this work we revisit their algorithm. While following their overall framework, we improve on each part of it. Svensson, Tarnawski, and Végh perform several steps of reducing ATSP to more and more structured instances. We avoid one of their reduction steps (to irreducible instances) and thus obtain a simpler and much better reduction to vertebrate pairs. Moreover, we show that a slight variant of their algorithm for vertebrate pairs has a much smaller approximation ratio. Overall, we improve the approximation ratio from 506 to 22 + ε for any ε > 0. We also improve the upper bound on the integrality ratio of the standard LP relaxation from 319 to 22. This is joint work with Jens Vygen. 
Follow us also on twitter and facebook. (To subscribe to the ICAFIT Algorithmic Colloquium mailing list with announcements send an email to igafitcolloquiumrequest@mimuw.edu.pl with subject SUBSCRIBE.)