Dynamic Algorithms
Recent Advances and Applications
Why this workshop?
The area of dynamic algorithms studies how to maintain useful information about an object undergoing adversarial updates, with a focus on minimizing the update time. It is closely related to other areas in TCS such as streaming and online algorithms.
In the last few years, we have witnessed a surge of exciting developments within dynamic algorithms. Furthermore, these breakthroughs have led to dramatic speed-ups of static algorithms for fundamental problems like maximum flow and linear programming. Behind the scenes, there are fascinating transfers of techniques between dynamic algorithms and other areas of TCS.
Our workshop will expose a general TCS audience to these exciting developments and interconnections.
Organizers
Sayan Bhattacharya (University of Warwick)
Thatchaphol Saranurak (University of Michigan)
Recordings
Link: videos recordings
Schedule
Wednesday June 22 (Room: Auditorium)
(9:15 - 9:45) Sayan and Thatchaphol
Invitation to dynamic algorithms(9:45 - 10:15) Richard Peng
Dynamic algorithms and optimization (Part 1)
Many recent developments in efficient algorithms are based on optimization routines. Such routines converge to optimum solutions via sequences of gradually changing subproblems, and have direct connections with dynamic algorithms. The first half of this talk will overview first- and second- order optimization algorithms, and their connections with (implicitly) maintaining solutions of dynamically changing linear systems. The second half of this talk will discuss the design of dynamic graph data structures tailored toward combinatorial optimization problems, including partitioning, sparsification, and vertex elimination algorithms.(10:15-10:45) Break
(10:45 - 11:15) Richard Peng
Dynamic algorithms and optimization (Part 2)(11:15 - 12:15) Amir Abboud, Sayan Bhattacharya, Anupam Gupta, Valerie King, Aaron Sidford
Future directions for dynamic algorithms: Panel and Q&A
Thursday June 23 (Room: Aula Magna DIAG)
Building: Dipartimento di Ingegneria Informatica Automatica e Gestionale "Antonio Ruberti" (Not in the same building as the one of Auditorium!)
Building: Dipartimento di Ingegneria Informatica Automatica e Gestionale "Antonio Ruberti" (Not in the same building as the one of Auditorium!)
(8:45 - 9:30) David Wajc
Dynamic matching algorithms and dynamic matching sparsifiers
Input sparsification is a common approach for speeding up algorithms for myriad computational tasks and models. In the context of dynamic algorithms, this approach goes back at least as far as the work of Eppstein et al. (FOCS'92, J.ACM'95). Over the last decade, this approach has had an outsized impact, most notably for the dynamic matching problem, where dynamic matching sparsifiers have played a key role in the numerous recent exciting developments for this problem. In this talk I will present some such developments building on the "equivalence" between dynamic matching and dynamic matching sparsifier maintenance.(9:30 - 10:15) Jan van den Brand
Dynamic algebraic algorithms for linear programs
Many algorithms use data structures that maintain properties of matrices undergoing some changes. Such data structure tools have recently lead to breakthroughs in continuous optimization algorithms such as linear program solvers. In this talk, I will present a subset of these tools that are widely applicable to various iterative algorithms, not just linear program solvers.(10:15-10:45) Break
(10:45 - 11:30) Gramoz Goranci
Vertex sparsification in dynamic algorithms and beyond
We’ll discuss a general algorithmic tool for designing dynamic graph algorithms known as vertex sparsification, a compression paradigm that reduces large graphs into smaller ones while preserving properties or features of interest. In particular, we show that black-box efficient constructions of vertex sparsifiers and their data-structure variants lead to dynamic maintenance of effective resistances on graphs. We will also briefly discuss the implications of this technique for the dynamic version of Laplacian systems and maximum flows.(11:30 - 12:15) Thatchaphol Saranurak
Using expanders for dynamic graph algorithms: a survey of tools
In the last few years, expanders have been used as a main tool in a large number of dynamic graph algorithms. I will explain why expanders can be useful for dynamic graph problems and how the recent algorithms can exploit expanders even if the input graph is not an expander. We will see all expander-related tools (known to me) and how these tools are being used in the literature.
Friday June 24 (Room: Auditorium)
(8:45 - 9:30) Omri Weinstein
Dynamic Data Structures in Machine Learning
Modern data analysis and deep-learning require efficient processing of giant matrices and dynamic datasets. This tutorial will highlight the role that dynamic data structures play in large-scale machine learning, by focusing on two key algorithmic primitives: Dynamic least-squares regression, and online (Kernel) matrix-vector multiplication.
We will describe a fairly general “dynamization” technique, which may be useful in other online matrix problems, and use it to prove a tight upper bound for dynamic regression. We will then prove a matching (conditional) lower bound, relating fine-grained complexity to numerical linear algebra. For online matrix-vector multiplication, we will mention how sub-quadratic (n*polylog(n)) time can be achieved for geometric Kernel matrix-vector multiply, even in dynamic settings.
(9:30 - 10:15) Eva Rotenberg
The Lazy-Greedy Path to Efficient Amortised Dynamic Algorithms
Recently, it was shown that dynamic planarity testing, i.e. maintaining whether a dynamic graph is planar, requires only amortised polylogarithmic update time per edge insertion or deletion [Holm, R. STOC'20]. The path towards this result goes via a lazy-greedy algorithm, together with a recourse analysis, that is, an analysis of how much the solution needs to change as the result of a local change in the input.
In this talk, I will start by showing an algorithm for bounded out-degree edge-orientations of dynamic sparse graphs [Brodal, Fagerberg WADS'99], which follows the same basic principle. The algorithm and its analysis are simple, elegant, and in fact teachable to students who have not seen dynamic graphs before. Then, I will tell about the problem of dynamic planarity testing, including an elegant amortised reduction to the case where planarity-violating edges may be detected and rejected [Eppstein, Galil, Italiano, Spencer '96], and sketch how a lazy-greedy approach using the notion of balanced embeddings gives an amortised polylog algorithm. Finally, I will present these balanced embeddings, which relate to the recourse analysis of dyanamic embeddings of dynamic graphs.
(10:15-10:45) Break
(10:45 - 11:30) Tomasz Kociumaka
Recent advances in dynamic string algorithms
In dynamic string algorithms, the objects undergoing updates are strings (finite sequences of characters from a given alphabet) or string collections. The study of such algorithms is over three decades old, but it has witnessed intense growth within the last few years. In my talk, I will discuss the standard ways to model dynamic strings and survey the recent results for dynamic versions of fundamental string processing problems. Moreover, I will present the central tool of dynamic string algorithms, locally consistent parsing, and reflect on future directions for this research area.(11:30 - 12:15) Junior-Senior meeting (informal)
Please put your name in this spreadsheet for signing up for the informal meeting
Learn More
Please email us (Sayan and Thatchaphol) if you have any suggestion on any further online materials. We will add them into the list.
Lectures
Erik Demaine's Lectures
Sayan's course on dynamic graph algorithms https://www.youtube.com/watch?v=HcNnSeD8CKA&list=PLhkiT_RYTEU2jSqGla9m-ErKH_PgX9D92&index=13 (Playlist)
Expository survey talks
Sayan's two-part talk on dynamic primal-dual algorithms for matching and set cover
Thatchaphol's talk on dynamic expander decomposition https://www.youtube.com/watch?v=4tTdU08_YBo
Thatchaphol's talk on congestion balancing technique https://www.youtube.com/watch?v=1X314koXKuU
Kasper's talks on dynamic cell-probe lower bounds
Jan's talk on interior point methods and dynamic data structures https://www.youtube.com/watch?v=8ZeUPacPGW0
Christian's introductory talks on dynamic graph algorithms [First, Second, Third]
Liam's survey talk on dynamic graph algorithms https://www.youtube.com/watch?v=oZGSdfyU_YU
Monika's talk on dynamic algorithms and their implementation https://www.youtube.com/watch?v=0U1AV-tDpQo
Long (technical) talks
David's talk on rounding dynamic fractional matchings https://www.youtube.com/watch?v=l_obg4ph5aM
Aaron's talk on dynamic shortest path https://www.youtube.com/watch?v=hzbJK1JnZck
Gramoz's talk on dynamic low-stretch embeddings https://www.youtube.com/watch?v=a1OhfZ-6qUw
Richard's talk dynamic spectral vertex sparsification https://www.youtube.com/watch?v=YyEA7ZZ3c5M
Omri's talk on dynamic cell-probe lower bounds https://www.youtube.com/watch?v=2fEq68S0pos