Richard Peng - A Survey on Fast Flow Algorithms
Flows, or combinations of paths, have origins in routing and assignment problems, and have wide ranges of applications. The talk will briefly overview progresses in data structures, continuous optimization, and graph approximations that were motivated by designing faster flow algorithms. Then it will discuss ways of combining such tools, with focus on recent developments of speeding up second order optimization methods using dynamic graph data structures.
Vera Traub - A Better-Than-2 Approximation for Weighted Tree Augmentation
The Weighted Tree Augmentation Problem (WTAP) is one of the most basic connectivity augmentation problems. It asks how to increase the edge-connectivity of a given graph from 1 to 2 in the cheapest possible way by adding some additional edges from a given set. We present an approximation algorithm for Weighted Tree Augmentation with approximation factor 1 + ln 2 + epsilon < 1.7. This is the first algorithm beating the longstanding factor of 2, which can be achieved through many standard techniques.
Mehtaab Sawhney - Online Vector Balancing
TBC
Jason Li - Deterministic Mincut in Almost-Linear Time
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.
Peyman Afshani - Lower Bounds for Semialgebraic Range Searching and Stabbing Problems
In the semialgebraic range searching problem, we are to preprocess n points in d-dimensional Euclidean space s.t., for any query range from a family of constant complexity semialgebraic sets, all the points intersecting the range can be reported or counted efficiently. When the ranges are composed of simplices, the problem is very well-understood: there are low-space solutions with linear space and with %%O(n^{1−1/d})%% query time and "fast query" structures that use %%O(n^d)%% space with polylogarithmic query time. However, for the general semialgebraic ranges, the problem has been much more mysterious. Relatively recently, the polynomial method breakthrough in discrete geometry led to low-space solutions with query time of %%\tilde{O}(n^{1-1/d})%% which almost matches the case of simplicies. Based on this, it was conjectured that the same could be done for the fast query case, meaning, getting polylogarithmic query times using only %%O(n^{d+o(1)})%% space but this open problem has stayed unresolved, even for very simple query ranges composed of circles.
Here, we disprove this conjecture. We give the first nontrivial lower bounds for semialgebraic range searching and the related problems. First, we show that any data structure for reporting the points between two concentric circles with %%Q(n)%% query time must use %%S(n)=Ω(n^{3−o(1)}/Q(n)^5)%% space, meaning, for polylogarithmic query time, almost cubic space is required. We also study the problem of reporting the pints between two polynomials of form %%Y=P(x)%% where %%P(x)%% is a polynomial of degree %%\Delta%%. Here, we show that for polylogarithmic query time, the space should be as large as %%\Omega(n^{\Delta+1-o(1)})%%. We also show similar lower bounds for the "dual" problem of semialgebraic stabbing problems.
Thatchaphol Saranurak - A Survey on Expander Graphs and their Usage in Dynamic Algorithms
TBC
Guy Blelloch - Parallel Minimum Cuts in %%O(m\log^2(n))%% Work and Low Depth
We present a randomized %%O(m\log^2n)%% work, %%O(\text{poly}\log n)%% depth parallel algorithm for minimum cut. This algorithm matches the work bounds of a recent sequential algorithm by Gawrychowski, Mozes, and Weimann [ICALP'20], and improves on the previously best parallel algorithm by Geissmann and Gianinazzi [SPAA'18], which performs %%O(m\log^4n)%% work in %%O(\text{poly}\log n)%% depth.
Our algorithm makes use of three components that might be of independent interest. Firstly, we design a parallel data structure that efficiently supports batched mixed queries and updates on trees. It generalizes and improves the work bounds of a previous data structure of Geissmann and Gianinazzi and is work efficient with respect to the best sequential algorithm. Secondly, we design a parallel algorithm for approximate minimum cut that improves on previous results by Karger and Motwani. We use this algorithm to give a work-efficient procedure to produce a tree packing, as in Karger's sequential algorithm for minimum cuts. Lastly, we design an efficient parallel algorithm for solving the minimum 2-respecting cut problem.
John Kallaugher - A Quantum Advantage for a Natural Streaming Problem
Data streaming, in which a large dataset is received as a “stream” of updates, is an important model in the study of space-bounded computation. Starting with the work of Le Gall [SPAA ‘06], it has been known that quantum streaming algorithms can use asymptotically less space than their classical counterparts for certain problems. However, so far, all known examples of quantum advantages in streaming are for problems that are either specially constructed for that purpose, or require many streaming passes over the input.
We give a one-pass quantum streaming algorithm for one of the best-studied problems in classical graph streaming—the triangle counting problem. Almost-tight parametrized upper and lower bounds are known for this problem in the classical setting; our algorithm uses polynomially less space in certain regions of the parameter space, resolving a question posed by Jain and Nayak in 2014 on achieving quantum advantages for natural streaming problems.
Mahsa Eftekhari - A Time and Space Optimal Stable Population Protocol Solving Exact Majority
With recent experimental breakthroughs in DNA nanotechnology and DNA computation, scientists are close to developing intelligent molecules that can communicate, perform tasks, and control matter at the nano level. Population protocols are a distributed computing model appropriate for modeling well-mixed physical systems such as chemical reaction networks and other physical systems where agents exchange information in pairwise interactions. Still, they have no control over their schedule of interaction partners.
In this talk, I will explain the ideas behind a recently developed protocol for the well-studied *majority* problem: determining in an initial population of n agents, each with one of two opinions, A or B, whether there are more A, more B, or a the. A *stable* protocol solves this problem with probability 1 by eventually entering a configuration in which all agents agree on a correct consensus decision of A, B, or T, from which the consensus cannot change. I describe a protocol that solves this problem using %%O(\log n)%% states (%%\log \log n + O(1)%% bits of memory) and optimal expected time %%O(\log n)%%. The number of states %%O(\log n)%% is known to be optimal for the class of polylogarithmic time stable protocols that are "output dominant" and "monotone". These are two natural constraints satisfied by our protocol, making it simultaneously time- and state-optimal for that class.