Helsinki CS Theory Seminar

The seminar is a weekly series of talks on a broad scope of CS theory hosted by the Aalto CS Theory Group. For the time being, all talks will be hosted on Zoom. On this page, you will find a brief overview of each talk, past and future. To subscribe to our mailing list, please visit this page. The subscribers receive a weekly mail on the current topic and a link for Zoom. If you missed the weekly mail, want to present your research, or have something else in mind, drop me an email to .

Upcoming Talks

Date and TimeSpeaker and TitleAbstractReference
Winter break
Winter break
Winter break Winter break
19th of January
14:15 (Helsinki time)
Michael Kapralov:
TBA
TBA
2nd of February
14:15 (Helsinki time)
Michal Dory:
TBA
TBA

Past Talks

Date and TimeSpeaker and TitleAbstractReference
1st of December
Non-standard time
17:15 (Helsinki time)
Nathan Klein:
A (Slightly) Improved Approximation Algorithm for Metric TSP
I will describe work in which we obtain a randomized $3/2-\epsilon$ approximation algorithm for metric TSP, for some $\epsilon>10^{-36}$. This slightly improves over the classical 3/2 approximation algorithm due to Christofides [1976] and Serdyukov [1978]. Following the approach of Oveis Gharan, Saberi, and Singh [2010], we analyze an algorithm which is a small modification of Christofides-Serdyukov: we obtain a TSP tour by adding a matching to a random spanning tree instead of one of minimum cost. The talk will focus on giving an overview of the key ideas involved to analyze the approximation factor of this algorithm, such as properties of random spanning trees and the structure of near minimum cuts.

I will also discuss a recent extension in which we show a $3/2-\epsilon$ bound on the integrality gap of the subtour elimination polytope. This is joint work with Anna Karlin and Shayan Oveis Gharan.
ArXiv
24th of November
14:15 (Helsinki time)
Roie Levin:
Random Order Set Cover is as Easy as Offline
We give a polynomial time algorithm for Online Set Cover with a competitive ratio of $O(\log mn)$ when the elements are revealed in random order, essentially matching the best possible offline bound of $O(\log n)$ and circumventing the $O(\log m \log n)$ lower bound known in adversarial order. We also extend the result to solving pure covering IPs when constraints arrive in random order. The algorithm is a multiplicative-weights-based round-and-solve approach we call Learn-Or-Cover. We maintain a coarse fractional solution that is neither feasible nor monotone increasing, but can nevertheless be rounded online to achieve the claimed guarantee (in the random order model). This gives a new offline algorithm for Set Cover that performs a single pass through the elements, which may be of independent interest.

This is joint work with Anupam Gupta and Gregory Kehne.
17th of November
14:15 (Helsinki time)
Kamyar Khodamoradi:
Local Search for (Stable) $k$-Means
In the classic (discrete) $k$-Median/Means problem, we are given a set of $n$ points in a metric alongside the parameter $k$, and our task is to choose $k$ of these points as centres such that the cost of connecting all the points to them is minimized. For $k$-Median, the cost of connecting a point to a set of centres is just the distance of the point to the closest centre in the set, and for $k$-Means, this cost is the square of the distance. In this talk, I will focus on a "promise'' variation of $k$-Median/Means where, 1) the metric is a Euclidean plane of constant dimensions, and 2) the instances of the problem are guaranteed to satisfy some stability constraint.

Stable optimization is a relatively young sub-field of optimization and approximation theory (introduced by Bilu and Linial in 2010), and can be seen as a "beyond the worst-case'' type of analysis. In the context of $k$-Means, an important notion of stability is that of perturbation resilience. An instance is called $\alpha$-perturbation resilient if there is a promise of a unique optimum solution which remains optimum even if the distances are (potentially non-uniformly) stretched by a factor of at most $\alpha$. Stable clustering instances have been studied to explain why heuristics such as Lloyd’s algorithm perform well in practice.

In this talk, I will show how $(1 + \varepsilon)$-stable instances of $k$-Means in bounded-dimension Euclidean metrics can be solved in polynomial time, using a simple local search algorithm. To give some background about the work, I will first roughly sketch how local search was applied to the (not necessarily stable) Euclidean instances of the problem (Friggstad et al., FOCS 2016) to obtain a $(1 + \varepsilon)$-approximation.
10th of November
14:15 (Helsinki time)
Oren Louidor:
A Scaling limit for the Cover Time of the Binary Tree
We consider a continuous time random walk on the rooted binary tree of depth $n$ with all transition rates equal to one and study its cover time, namely the time until all vertices of the tree have been visited. We prove that, normalized by $2^{n+1} n$ and then centered by $(\log 2) n - \log n$, the cover time admits a weak limit as the depth of the tree tends to infinity. The limiting distribution is identified as that of a Gumbel random variable with rate one, shifted randomly by the logarithm of the sum of the limits of the derivative martingales associated with two negatively correlated discrete Gaussian free fields on the infinite version of the tree. The existence of the limit and its overall form were conjectured in the literature. Our approach is quite different from those taken in earlier works on this subject and relies in great part on a comparison with the extremal landscape of the discrete Gaussian free field on the tree.

Joint work with Aser Cortines and Santiago Saglietti.
ArXiv
27th of October
14:15 (Helsinki time)
Rustam Latypov:
Memory Efficient Massively Parallel Algorithms for LCL Problems on Trees
We pioneer the low-space Massively Parallel Computation (MPC) complexity landscape for a family of fundamental graph problems on trees. We give a general method that solves most locally checkable labeling (LCL) problems exponentially faster in the low-space MPC model than in the LOCAL message passing model. In particular, we show that all solvable LCL problems on trees can be solved in $O(\log n)$ time (high-complexity regime) and that all LCL problems on trees with deterministic complexity $n^{o(1)}$ in the LOCAL model can be solved in $O(\log \log n)$ time (mid-complexity regime). We emphasize that we solve LCL problems on constant degree trees, our algorithms are deterministic, and they work in the low-space MPC model, where local memory is $O(n^\delta)$ for $\delta \in (0,1)$ and global memory is $O(m)$.

For the high-complexity regime, their are two key ingredients. One is a novel $O(\log n)$ time tree rooting algorithm, which may be of independent interest. The other ingredient is a novel pointer-chain technique and analysis that allows us to solve any solvable LCL problem on trees in $O(\log n)$ time. For the mid-complexity regime, we adapt the approach by Chang and Pettie [FOCS'17], who gave a canonical LOCAL algorithm for solving LCL problems on trees. For the special case of 3-coloring trees, which is a natural LCL problem with LOCAL time complexity $n^{o(1)}$, we show that our analysis is tight, as it matches the conditional $\Omega(\log \log n)$ lower bound for component-stable algorithms.
13th of October
14:15 (Helsinki time)
Sándor Kisfaludi-Bak:
The traveling salesman and the Steiner tree with flat neighborhoods
In the classic Euclidean traveling salesman problem, we are given n points in the Euclidean plane, and the goal is to find the shortest round trip that visits all the points. The Steiner tree asks for the shortest tree that can connect these points. An interesting variant of these problems is when instead of visiting points, we are asked to visit n "neighborhoods". A neighborhood could be any sort of geometric object; the goal is then to visit at least one point in each object. For example, we could be given a set of affine subspaces (often called flats) in $d$-dimensional Euclidean space, and the goal is to find the shortest round trip or tree that intersects each subspace. We will see how the 2-dimensional problems with line neighborhoods can be tackled, and see how the optimum tour for hyperplane neighborhoods ($(d-1)$-dimensional flats) can be efficiently approximated in higher dimensions. It turns out that these neighborhood problems have a different computational complexity than the classic problems with points: they require a novel approach for the hyperplane case, while the case of lower-dimensional flats remain largely mysterious.
6th of October
Non-standard time
17:15 (Helsinki time)
Yakov Nekrich:
Dynamic Point Location in Optimal Time.
In the dynamic point location problem we maintain a planar subdivision under insertions and deletions of segments so that for any query point $q$ the polygon containing $q$ can be found efficiently. In the dynamic vertical ray shooting problem we maintain a set of non-intersecting segments on a plane, so that for an arbitrary query point $q$ the highest segment immediately below $q$ can be found efficiently, where the segment immediately below $q$ is the first segment hit by a downward vertical ray from $q$. Vertical ray shooting and point location are closely connected problems: a data structure for vertical ray shooting can be transformed into a data structure for planar point location. In this talk we present a fully-dynamic data structure that supports point location queries in a connected planar subdivision with $n$ edges. Our data structure uses $O(n)$ space, answers queries in $O(\log n)$ time, and supports updates in $O(\log n)$ time. Our solution is based on a data structure for vertical ray shooting queries that supports queries and updates in $O(\log n)$ time. Paper
29th of September
14:15 (Helsinki time)
Noam Touitou:
Flow Time Scheduling with Uncertain Processing Time
We consider the problem of online scheduling on a single machine in order to minimize weighted flow time. The existing algorithms for this problem (STOC '01, SODA '03, FOCS '18) all require exact knowledge of the processing time of each job. This assumption is crucial, as even a slight perturbation of the processing time would lead to polynomial competitive ratio. However, this assumption very rarely holds in real-life scenarios.
In this paper, we present the first algorithm for weighted flow time which do not require exact knowledge of the processing times of jobs. Specifically, we introduce the Scheduling with Predicted Processing Time (SPPT) problem, where the algorithm is given a prediction for the processing time of each job, instead of its real processing time. For the case of a constant factor distortion between the predictions and the real processing time, our algorithms match all the best known competitiveness bounds for weighted flow time -- namely $O(\log P)$, $O(\log D)$ and $O(\log W)$, where $P, D, W$ are the maximum ratios of processing times, densities, and weights, respectively. For larger errors, the competitiveness of our algorithms degrades gracefully.
ArXiv
22nd of September
14:15 (Helsinki time)
Chetan Gupta:
Derandomizing Isolation Lemma for Special Classes of Graphs
Isolation lemma states that if we randomly assign polynomially large weights to the elements of a set $S$ then for any family $F$ of subsets of $S$, the minimum weight subset in F will be unique with high probability. Isolation lemma has found numerous applications in complexity theory since its introduction. In this talk, I will talk about its application in the two fundamental problems in complexity theory, perfect matching and directed graph reachability.

In the perfect matching problem, we want to find out whether a given graph has a perfect matching or not. Perfect matching problem is known to have a polynomial-time sequential algorithm. In complexity theory, most often, for every problem that has a polynomial-time sequential algorithm, people try to find an efficient parallel algorithm (NC algorithm) for the same in order to make progress towards P vs NC question. But the question whether there exists an efficient parallel algorithm for perfect matching or not has been elusive so far. Efforts to find an efficient parallel algorithm for perfect matching spurred powerful tools like isolation lemma. It was shown that if we can derandomize the isolation lemma for perfect matchings, that is, if we can efficiently construct polynomial-size weights for the edges of a graph such that minimum weight perfect matching in the graph is unique then the perfect matching problem can be solved in SPL, which is a small subclass of NC.

In the graph reachability problem, given a directed graph and two vertices, we are asked whether there exists a path from one vertex to another or not. Reachability is a complete problem for complexity class NL, which is a class of problems that can be solved by nondeterministic Turing machines in logspace. The question whether reachability can be solved by an unambiguous logspace Turing machine (UL) or not is still open. It was shown that if we can derandomize the isolation lemma for paths, then reachability can be solved by a UL machine. This talk will explain how we can derandomize the isolation lemma for $O(\log n)$ genus graphs and single-crossing minor free graphs to obtain an SPL bound for bipartite perfect matching and UL bound for reachabilty, in these two classes.
Slides
ArXiv
MFCS
15th of September
14:15 (Helsinki time)
Laurent Feuilloley:
The Secretary Problem with Independent Sampling
The secretary problem is a classic online decision problem. In this problem, an adversary first chooses some n numbers, then these numbers are shuffled at random and presented to the player one by one. For each number, the player has two options: discard the number and continue, or keep the number and stop the game. The player wins if she kept the highest number of the whole set. It is clearly not possible to win all the time: when one decides to stop there might be a higher number in the rest of the sequence, and when one discards a number, it might actually be the highest of the sequence. But surprisingly one can win with probability $1/e$.

An issue with the secretary problem is that it assumes that the player has absolutely no information about the numbers, which reduces its applicability. A recent research direction is to understand what happens when one knows a distribution or samples etc. We study a simple such setting for which we prove tight results. Interestingly, some of the lower bound techniques we use are inspired by ideas from distributed graph algorithms.
ArXiv
8th of September
Non-standard time
17:00 (Helsinki time)
Jan van den Brand:
Unifying Matrix Data Structures - Simplifying and Speeding up Iterative Algorithms
Many algorithms use data structures that maintain properties of matrices undergoing some changes. The applications are wide-ranging and include for example matchings, shortest paths, linear programming, semi-definite programming, convex hull and volume computation. Given the wide range of applications, the exact property these data structures must maintain varies from one application to another, forcing algorithm designers to invent them from scratch or modify existing ones. Thus it is not surprising that these data structures and their proofs are usually tailor-made for their specific application and that maintaining more complicated properties results in more complicated proofs. In this talk, I present a unifying framework that captures a wide range of these data structures. The simplicity of this framework allows us to give short proofs for many existing data structures regardless of how complicated the to be maintained property is. We also show how the framework can be used to speed up existing iterative algorithms, such as the simplex algorithm. ArXiv
21st of July
14:15 (Helsinki time)
Iftach Haitner:
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
In a distributed coin-flipping protocol, Blum [ACM Transactions on Computer Systems '83], the parties try to output a common (close to) uniform bit, even when some adversarially chosen parties try to bias the common output. In an adaptively secure full-information coin flip, Ben-Or and Linial [FOCS '85], the parties communicate over a broadcast channel and a computationally unbounded adversary can choose which parties to corrupt during the protocol execution. Ben-Or and Linial proved that the n-party majority protocol is resilient to $O(\sqrt{n})$ corruptions (ignoring poly-logarithmic factors), and conjectured this is a tight upper bound for any n-party protocol (of any round complexity). Their conjecture was proved to be correct for limited variant of single-turn (each party sends a single message) single-bit (a message is one bit) protocols, Lichtenstein, Linial, and Saks [Combinatorica '89], symmetric protocols Goldwasser, Kalai, and Park [ICALP '15], and recently for (arbitrary message length) single-turn protocols Kalai, Komargodski, and Raz [DISC '18]. Yet, the question for many-turn (even single-bit) protocols was left completely open.

In this work we close the above gap, proving that no n-party protocol (of any round complexity) is resilient to $\omega(\sqrt{n})$ (adaptive) corruptions. That is, up to polylog factors, the single-bit, single-message majority protocol is the optimal protocol against adaptive corruptions.

Joint work with Yonatan Karidi-Heller.
ArXiv
30th of June
14:15 (Helsinki time)
Bernhard Haeupler:
The Quest for Universally-Optimal Distributed Algorithms
Many distributed optimization algorithms achieve an existentially-optimal round complexity of ($\tilde{O}(\sqrt{n} + D)$, i.e., there exists some pathological worst-case topology on which no algorithm can be faster. However, most networks of interest allow for exponentially faster algorithms. This motivates two questions:
(1) What network topology parameters determine the complexity of distributed optimization?
(2) Are there universally-optimal algorithms that are as fast as possible on every single topology?

This talk provides an overview over the freshly-completed 6-year program that affirmatively resolves these 25-year-old open problems for a wide class of global network optimization problems including MST, $(1+\epsilon)$-min cut, various approximate shortest path problems, sub-graph connectivity, etc.. In particular, we provide several equivalent graph parameters that are tight universal lower bounds for the above problems, fully characterizing their inherent complexity. We also give the first universally-optimal algorithms approximately achieving this complexity on every topology.

The quest for universally-optimal distributed algorithms required novel techniques that also answer fundamental (open) questions in seemingly unrelated fields, such as, network information theory, approximation algorithms, (oblivious) packet routing, (algorithmic & topological) graph theory, and metric embeddings. Generally, the problems addressed in these fields explicitly or implicitly ask to jointly optimize $\ell_\infty$ & $\ell_1$ parameters such as congestion & dilation, communication rate & delay, capacities & diameters of subnetworks, or the makespan of packet routings. In particular, results obtained on the way include the following firsts: (Congestion+Dilation)-Competitive Oblivious Routing, Network Coding Gaps for Completion-Times, Hop-Constrained Expanders & Expander Decompositions, Bi-Criteria (Online / Demand-Robust) Approximation Algorithms for many Diameter-Constrained Network Design Problems (e.g., (Group) Steiner Tree/Forest), Makespan-Competitive (Compact and Distributed) Routing Tables, and (Probabilistic) Tree Embeddings for Hop-Constrained Distances.

(joint work with Mohsen Ghaffari, Goran Zuzic, Ellis D. Hershkowitz, David Wajc, Jason Li, Harald Raecke, Taisuke Izumi)
ArXiv
16th of June
14:15 (Helsinki time)
Yael Hitron:
Distributed CONGEST Algorithms Against Adversarial Edges
In this talk, I will present broadcast algorithms in the adversarial CONGEST model. In this model, there is an adaptive byzantine adversary that controls some edges (or vertices) $F$ in the input communication graph. The adversary sees the entire communication graph, as well as the random coins of the nodes, while maliciously manipulating the messages sent through the $F$ edges (unknown to the nodes). The communication occurs as in the standard CONGEST model Our two key results for $n$-node graphs of diameter $D$ are as follows:

1. For $|F|=1$, there is a deterministic broadcast algorithm that runs in $\widetilde{O}(D^2)$ rounds, provided that the graph is $3$ edge-connected (which is necessary). This round complexity beats the natural barrier of $O(D^3)$ rounds, the existentially lower bound on the maximal length of $3$ edge-disjoint paths between a given pair of nodes in $G$. This algorithm can be extended to a $\widetilde{O}(D^{O(t)})$-round algorithm against $|F|=t$ adversarial edges in $(2t+1)$ edge-connected graphs.

2. For expander graphs with edge-connectivity $t=\Omega(\log n)$, we provide a considerably improved broadcast algorithm with $O(t' \log ^2 n)$ rounds, provided that the adversary controls at most $t'=O(\sqrt{t/\log n})$ edges. I will also present some concrete open problems.

This is joint work with Merav Parter.
9th of June
14:15 (Helsinki time)
Krzysztof Nowicki:
A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique
In this talk I'll present a simple deterministic algorithm for the MST problem that needs only $O(1)$ rounds of Congested Clique. The algorithm can be also applied in the MPC model, as long as the local memory of a single machine is $O(n)$.The key technical contribution is an algorithm for the maximal (in the sense of inclusion) spanning forest that does not rely on any randomized techniques (e.g., graph sketches, 1-out sampling, uniform sampling) used to obtain all previous $o(\log \log n)$ round algorithms. ArXiv
19th of May
14:15 (Helsinki time)
Anton Bernshteyn:
Distributed algorithms and continuous combinatorics
The topic of this talk is a recently discovered connection between two seemingly disparate fields: distributed computing and descriptive combinatorics. Distributed computing is the area of computer science concerned with problems that can be solved efficiently by a (finite) decentralized network of processors. Descriptive combinatorics, on the other hand, studies combinatorial problems on infinite graphs under additional topological or measure-theoretic regularity constraints and is largely motivated by questions in logic and ergodic theory. It turns out that these two areas are closely related to each other, and there are formal ways of translating results from one context to the other one. In particular --- and this is the main focus of this talk --- a local coloring problem can be solved by an efficient deterministic distributed algorithm if and only if it admits a continuous solution. ArXiv
12th of May
14:15 (Helsinki time)
Joel Rybicki:
Fast Population Protocols on Graphs
In the stochastic population protocol model, a collection of indistinguishable, resource-limited nodes reside on a graph and collectively solve tasks via pairwise interactions. In each interaction, two randomly chosen neighbours first read each other's states, and then update their local states. A recent line of research has established trade-offs between time and space complexity for various fundamental tasks, such as majority and leader election, when the underlying interaction graph is a clique.

In this talk, we consider the more general setting of arbitrary interaction graphs and introduce a technique for simulating protocols designed for fully-connected networks in any connected regular graph. The technique allows us to automatically transfer synchronous algorithms designed for the clique into the asynchronous setting on regular graphs. As an application of this result, we obtain fast and space-efficient population protocols for leader election and exact majority on graphs with good expansion properties. The talk is based on joint work with Dan Alistarh and Rati Gelashvili.
ArXiv
5th of May
14:15 (Helsinki time)
Tuomas Hakoniemi:
Feasible interpolation for algebraic proof systems
Feasible interpolation is a framework introduced by Krajíček in 90's for extracting computational content from proofs in formal proof systems. Although originally conceived as a means to prove lower bounds on size of proofs from lower bounds on different computational models, the framework finds also non-trivial applications in the opposite direction. In this talk we consider two algebraic proof systems, Polynomial Calculus and Sums-of-Squares, and give a form of feasible interpolation for these systems. These systems can be used to show the infeasibility of a set of polynomial constraints, and with a suitable encoding of clauses into polynomial constraints, the systems can be used as refutation systems for CNFs. Our results do not yield any new unconditional lower bounds for the proof systems. However, as a consequence for feasible interpolation for Sums-of-Squares, we obtain a novel polynomial time algorithm for separating $(k-1)$-colorable graphs from those containing a $k$-clique. Paper
28th of April
14:15 (Helsinki time)
Christoph Grunau:
A gap in the Randomized Local Computation Complexity Landscape
The Local Computation Algorithm (LCA) model is a popular model in the field of sublinear-time algorithms that measures the complexity of an algorithm by the number of probes the algorithm makes in the neighborhood of one node to determine that node’s output. In this talk, I show that every randomized LCA algorithm for a locally checkable problem with a probe complexity of $o(\sqrt{\log n})$ can be turned into a deterministic LCA algorithm with a probe complexity of $O(\log^* n)$. I also show how additional ideas lead to an $\Omega(log n)$ lower bound for the Lovasz Local Lemma (LLL) on constant degree graphs. This talk is based on joint work with Sebastian Brandt and Vasek Rozhon. ArXiv
21th of April
14:15 (Helsinki time)
Sorrachai Yingchareonthawornchai:
Vertex Connectivity in Poly-logarithmic Max-flows
The vertex connectivity of an $m$-edge $n$-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in $\widetilde{O}(m^α)$ time for any $\alpha \geq 1$, if there is a $m^α$-time maxflow algorithm.
Using the current best maxflow algorithm that runs in $m^{4/3+o(1)}$ time (Kathuria, Liu and Sidford, FOCS 2020), this yields an $m^{4/3+o(1)}$-time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an $\widetilde{O}(mn)$-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an $o(mn)$ running time was known before our work, even if we assume an $\widetilde{O}(m)$-time maxflow algorithm.
ArXiv
14th of April
14:15 (Helsinki time)
Yuval Gil:
Twenty-Two New Approximate Proof Labeling Schemes
Introduced by Korman, Kutten, and Peleg (Distributed Computing 2005), a proof labeling scheme (PLS) is a system dedicated to verifying that a given configuration graph satisfies a certain property. It is composed of a centralized prover, whose role is to generate a proof for yes-instances in the form of an assignment of labels to the nodes, and a distributed verifier, whose role is to verify the validity of the proof by local means and accept it if and only if the property is satisfied. To overcome lower bounds on the label size of PLSs for certain graph properties, Censor-Hillel, Paz, and Perry (SIROCCO 2017) introduced the notion of an approximate proof labeling scheme (APLS) that allows the verifier to accept also some no-instances as long as they are not "too far" from satisfying the property.

The goal of the current paper is to advance our understanding of the power and limitations of APLSs. To this end, we formulate the notion of APLSs in terms of distributed graph optimization problems (OptDGPs) and develop two generic methods for the design of APLSs. These methods are then applied to various classic OptDGPs, obtaining twenty-two new APLSs. An appealing characteristic of our APLSs is that they are all sequentially efficient in the sense that both the prover and the verifier are required to run in (sequential) polynomial time. On the negative side, we establish “combinatorial” lower bounds on the label size for some of the aforementioned OptDGPs that demonstrate the optimality of our corresponding APLSs. For other OptDGPs, we establish conditional lower bounds that exploit the sequential efficiency of the verifier alone (under the assumption that NP ≠ co-NP) or that of both the verifier and the prover (under the assumption that P ≠ NP, with and without the unique games conjecture).
ArXiv
7th of April
14:15 (Helsinki time)
Václav Rozhoň:
The ID Graph Trick and its Applications to Lower Bounds in the LOCAL and LCA Model
We will talk about the so-called ID graph: this is a new trick useful for proving lower bounds in distributed models of computation. We will show how it can be used to simplify the famous lower bound for the Lovász Local Lemma in the distributed LOCAL model and then we will discuss how it can be used to prove a lower bound for the same problem in the Local Computation Algorithm model.
We also discuss the original usage of the trick: to translate results from the field of descriptive combinatorics to distributed algorithms.

Joint work with Sebastian Brandt, Jan Grebík, Christoph Grunau
ArXiv
31st of March
14:15 (Helsinki time)
Juho Hirvonen:
Classifying Convergence Complexity of Nash Equilibria in Graphical Games Using Distributed Computing Theory
Graphical games are a framework for modelling games where an underlying graph determines how the actions of players affect each other. The utility of each player depends only on its own strategy and the strategy of its neighbours. In this context many fundamental equilibrium concepts are localised: for example, the strategies of the players form a Nash equilibrium if and only if no player can unilaterally improve its current strategy with respect to its neighbours.

Systems modelled as graphical games can also be naturally seen as distributed systems. Assuming that a system is converging to a Nash equilibrium, it is implicitly solving the corresponding computational task of finding a Nash equilibrium. Since Nash equilibria of graphical games are localised, finding one is a locally verifiable task. This family of problems has been studied widely in the theory of distributed graph algorithms, and it is therefore possible to use distributed complexity theory to understand and classify the equilibria of graphical games.

I will present our work formalising this connection. We give examples of basic graphical games and show how theory of distributed computing can be used to understand them.
Paper
17th of March
14:15 (Helsinki time)
Andras Papp:
Computational Aspects of Financial Networks
We study financial networks with debt contracts and credit default swaps between specific pairs of banks. Given such a financial system, we want to decide which of the banks are in default, and how much of their liabilities can these defaulting banks pay. There can easily be multiple different solutions to this problem, leading to a situation of default ambiguity and a range of possible solutions to implement for a financial authority.

We first study these financial networks from a game-theory perspective, analyzing the incentives of banks, and some simple operations they could execute in order to influence the outcome to their advantage. We show that if multiple banks try to execute these operations simultaneously, then this can easily result in classical game theoretic situations like the prisoner's dilemma or the dollar auction game.

We then analyze these financial networks in a sequential model where banks announce their default one at a time, and the system evolves in a step-by-step manner. We show that such a dynamic process can go on indefinitely, or last for an exponential number of steps before an eventual stabilization. We also study how the ordering of announcements affects the final outcome, and show that even for a single bank, finding the best time to announce a default is already an NP-hard problem.
Paper
Paper
10th of March
14:15 (Helsinki time)
Petteri Kaski:
Error-Correcting and Verifiable Parallel Inference in Graphical Models
We present a novel framework for parallel exact inference in graphical models. Our framework supports error-correction during inference and enables fast verification that the result of inference is correct, with probabilistic soundness. The computational complexity of inference essentially matches the cost of w-cutset conditioning, a known generalization of Pearl's classical loop-cutset conditioning for inference. Verifying the result for correctness can be done with as little as essentially the square root of the cost of inference. Our main technical contribution amounts to designing a low-degree polynomial extension of the cutset approach, and then reducing to a univariate polynomial employing techniques recently developed for noninteractive probabilistic proof systems. This is joint work with Negin Karimi (Aalto University) and Mikko Koivisto (University of Helsinki). Paper
24th of February
14:15 (Helsinki time)
Michele Scquizzato:
Tight Bounds for Parallel Paging and Green Paging
In the parallel paging problem, there are p processors that share a cache of size \(k\). The goal is to partition the cache among the processors over time in order to minimize their average completion time. For this long-standing open problem, we give tight upper and lower bounds of Θ(log p) on the competitive ratio with O(1) resource augmentation.

A key idea in both our algorithms and lower bounds is to relate the problem of parallel paging to the seemingly unrelated problem of green paging. In green paging, there is an energy-optimized processor that can temporarily turn off one or more of its cache banks (thereby reducing power consumption), so that the cache size varies between a maximum size k and a minimum size k/p. The goal is to minimize the total energy consumed by the computation, which is proportional to the integral of the cache size over time.

We show that any efficient solution to green paging can be converted into an efficient solution to parallel paging, and that any lower bound for green paging can be converted into a lower bound for parallel paging, in both cases in a black-box fashion. We then show that, with O(1) resource augmentation, the optimal competitive ratio for deterministic online green paging is Θ(log p), which, in turn, implies the same bounds for deterministic online parallel paging.
Paper
17th of February
14:15 (Helsinki time)
Faour Salwa:
Approximating Bipartite Minimum Vertex Cover in the CONGEST Model
In this talk, I present how one can achieve efficient distributed algorithms for the minimum vertex cover problem in bipartite graphs in the CONGEST model for both the randomized and deterministic setting. This is based on a joint work with Fabian Kuhn (University of Freiburg).

From Kőnig’s theorem, it is well known that in bipartite graphs the size of a minimum vertex cover is equal to the size of a maximum matching. First, we show that together with an existing \( O ( n \log n )\)-round algorithm for computing a maximum matching, the constructive proof of Kőnig's theorem directly leads to a deterministic \( O ( n \log n )\)-round CONGEST algorithm for computing a minimum vertex cover. We then show that by adapting the construction, we can also convert an approximate maximum matching into an approximate minimum vertex cover. Given a \((1-\delta)\)-approximate matching for some \( \delta > 1\), we show that a \((1+O(\delta))\)-approximate vertex cover can be computed in time \(O(D+\poly (\frac{\log n}{\delta}))\), where D is the diameter of the graph. Finally when combining with known graph clustering techniques, for any \(\eps \in (0,1]\), this leads to a \(\poly(\frac{\log n}{\eps})\)-time deterministic and also to a slightly faster and simpler randomized \(O(\frac{\log n}{\eps^3})\)-round CONGEST algorithm for computing a $(1+\eps)$-approximate vertex cover in bipartite graphs.

For constant \(\eps\), the randomized time complexity matches the \(\Omega(\log n)\) lower bound (Göös, Suomela 2014) for computing a \((1+\eps)\)-approximate vertex cover in bipartite graphs even in the LOCAL model. Our results are also in contrast to the situation in general graphs, where it is known that computing an optimal vertex cover requires \(\tilde{\Omega}(n^2)\) rounds in the CONGEST model and where it is not even known how to compute any \((2-\eps)\)-approximation in time \(o(n^2)\).
Paper
3rd of February
14:15 (Helsinki time)
Orr Fischer:
A Distributed Algorithm for Directed Minimum-Weight Spanning Tree
In the directed minimum spanning tree problem (DMST, also called minimum weight arborescence), the network is given a root node $r$, and needs to construct a minimum-weight directed spanning tree, rooted at $r$ and oriented outwards. In this paper we present the first sub-quadratic DMST algorithms in the distributed CONGEST network model, where the messages exchanged between the network nodes are bounded in size. We consider three versions: a model where the communication links are bidirectional but can have different weights in the two directions; a model where communication is unidirectional; and the Congested Clique model, where all nodes can communicate directly with each other.

Our algorithm is based on a variant of Lovasz' DMST algorithm for the PRAM model, and uses a distributed single-source shortest-path (SSSP) algorithm for directed graphs as a black box.

In the bidirectional CONGEST model, our algorithm has roughly the same running time as the SSSP algorithm; using the state-of-the-art SSSP algorithm, we obtain a running time of $\widetilde{O}(n^{1/2}D^{1/4} + D))$ rounds for the bidirectional communication case.

For the unidirectional communication model we give an $\widetilde{O}(n)$ algorithm, and show that it is nearly optimal. And finally, for the Congested Clique, our algorithm again matches the best known SSSP algorithm: it runs in $\widetilde{O}(n^{1/3})$ rounds.

On the negative side, we adapt an observation of Chechik in the sequential setting to show that in all three models, the DMST problem is at least as hard as the $(s,t)$-shortest path problem. Thus, in terms of round complexity, distributed DMST lies between single-source shortest path and $(s,t)$-shortest path.
Paper
20th of January
14:15 (Helsinki time)
Vanni Noferini:
Walk this way
In complex network analysis, centrality measures are nonnegative valued functions defined on the nodes of a graph that measure the relative importance of each node. Applications include, for instance, singling out the most influential users of a social network, or identifying potential superspreaders within the context of a disease epidemic. Due to the existence of efficient computational algorithms based on numerical linear algebra, centrality measures based on walks are particularly popular. However, in certain applications it is desirable to refine the underlying combinatorics, by neglecting certain types of walks, in order to obtain more significant results.

After a gentle introduction including some classical results in this research area, I will discuss some recently proposed definitions of centrality measures that only count walks that do not backtrack, or more generally do not include cycles of length $\leq k$. I will focus both on theoretical properties of these measures and on computational issues. The talk is based on collaborative work with F. Arrigo (Strathclyde), P. Grindrod (Oxford) and D. Higham (Edinburgh).
13th of January
14:15 (Helsinki time)
Jonni Virtema:
Descriptive complexity of real computation and probabilistic team semantics
In this talk I survey my recent joint work with Miika Hannula (Helsinki), Juha Kontinen (Helsinki), and Jan Van den Bussche (Hasselt) on logics and complexity in a setting that incorporates real numbers as first-class citizens.

Background:
Metafinite model theory (Grädel & Gurevich 1998) generalizes the approach of finite model theory by shifting to two-sorted structures that extend finite structures with another (often infinite) domain with some arithmetic (such as the reals with multiplication and addition), and weight functions bridging the two sorts. Finite structures enriched with real arithmetic are called R-structures. Blum-Shub-Smale machines (Blum, Shub & Smale 1989), BSS machine for short, are essentially random access machines with registers that can store real numbers and which can compute arithmetic operations on reals in a single time step. In addition for recognizing languages over the reals, BSS machines can also be used to recognize languages on the Boolean alphabeth {0,1}; e.g. Boolean languages recognizable by BSS-machiness in non-determinitic polynomial time coincides with the complexity class existsR (problems PTIME reducible to the existential theory of the reals) which lies somewhere between NP and PSPACE (defined with Turing machines). NP on BSS machines was logically captured by a variant of existential second-order logic over R-structures in (Grädel & Meer 1995).

Our contribution:
We study descriptive complexity of logics in the setting of probabilistic team semantics. This is a family of logics built-up from atomic expressions stating quantitative notions of dependence between random variables. E.g., probabilistic independence logic is built around an atomic statement that declares conditional probabilistic independence between tuples of random variables. Formulae, in this setting, describe properties of real-weighted distributions over first-order assignments. Hence, it turns out, that the descriptive complexity of related logics lie in the realm of BSS-machines. For pinpointing the exact complexity of logics in the probabilistic team semantics setting, we introduced a novel restricted variant of BSS machines, coined "separate-branching BSS-machines" or SBSS-machines. This led to various connections between logics using probabilistic team semantics, complexity classes defined via SBSS-machines, complexity classes defined via Turing machines, and restrictions of the variant of existential second-order logic of Grädel and Meer.
Paper
ArXiv
16th of December
14:15 (Helsinki time)
Merav Parter:
An Algorithmic Perspective for Spiking Neural Networks
Understanding how the brain works, as a computational device, is a central challenge of modern neuroscience and artificial intelligence. Different research communities approach this challenge in different ways, including studies that examine neural network structure as a clue to computational function, functional imaging that studies neural activation patterns, theoretical work using simplified models of neural computation, and engineering of complex neural-inspired machine learning architectures. The talk will be devoted to a line of works that approaches this problem using techniques from distributed computing theory and other branches of theoretical computer science. We will present a scientific perspective on the area, modeling neural networks as computational platforms and studying computability and costs within these models.

We will focus on a collection of abstract problems inspired by problems that are solved in actual brains, such as problems of focus, time estimation, recognition, and memory. The goal is to design efficient algorithms (networks) for solving these problems, and analyze them in terms of static costs such as network size and dynamic costs such as the time to converge to a correct solution.

The talk will also discuss the barriers of asynchronous neural computation from an algorithmic perspective, and the role of randomness in neural computation. If time allows, we will mention some interesting relations to the area of streaming algorithms.

Based on several joint works with Yael Hitron, Nancy Lynch, Cameron Musco and Gur Perry.
9th of December
14:15 (Helsinki time)
William Moses Jr.:
Singularly Optimal Randomized Leader Election
This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks. Our main result is a randomized distributed leader election algorithm for asynchronous complete networks that is essentially (up to a polylogarithmic factor) singularly optimal. Our algorithm uses O(n) messages with high probability and runs in O(\log^2 n) time (with high probability) to elect a unique leader. The O(n) message complexity should be contrasted with the \Omega(n \log n) lower bounds for the deterministic message complexity of leader election algorithms (regardless of time), proven by Korach, Moran, and Zaks (TCS, 1989) for asynchronous algorithms and by Afek and Gafni (SIAM J. Comput., 1991) for synchronous networks. Hence, our result also separates the message complexities of randomized and deterministic leader election. More importantly, our (randomized) time complexity of O(\log^2 n) for obtaining the optimal O(n) message complexity is significantly smaller than the long-standing \tilde{\Theta}(n) time complexity obtained by Afek and Gafni and by Singh (SIAM J. Comput., 1997) for message optimal (deterministic) election in asynchronous networks. Afek and Gafni also conjectured that \tilde{\Theta}(n) time would be optimal for message-optimal asynchronous algorithms. Our result shows that randomized algorithms are significantly faster.

Turning to synchronous complete networks, Afek and Gafni showed an essentially singularly optimal deterministic algorithm with O(\log n) time and O(n \log n) messages. Ramanathan et al. (Distrib. Comput. 2007) used randomization to improve the message complexity, and showed a randomized algorithm with O(n) messages but still with O(\log n) time (with failure probability O(1 / \log^{\Omega(1)}n)). Our second result shows that synchronous complete networks admit a tightly singularly optimal randomized algorithm, with O(1) time and O(n) messages (both bounds are optimal). Moreover, our algorithm's time bound holds with certainty, and its message bound holds with high probability, i.e., 1-1/n^c for constant c.

Our results demonstrate that leader election can be solved in a simultaneously message and time-efficient manner in asynchronous complete networks using randomization. It is open whether this is possible in asynchronous general networks.

This talk is based on joint work with Shay Kutten, Gopal Pandurangan, and David Peleg which was published at DISC 2020.
Paper
2nd of December
14:15 (Helsinki time)
Shreyas Pai:
Sample-and-Gather: Fast Ruling Set Algorithms in the Low-Memory MPC Model
Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the low-memory Massively Parallel Computation (MPC) model (e.g., Behnezhad et al. PODC 2019; Ghaffari-Uitto SODA 2019), we investigate the complexity of ruling set problems in this model. The MPC model has become very popular as a model for large-scale distributed computing and it comes with the constraint that the memory-per-machine is strongly sublinear in the input size. For graph problems, extremely fast MPC algorithms have been designed assuming Õ(n) memory-per-machine, where n is the number of nodes in the graph (e.g., the O(log log n) MIS algorithm of Ghaffari et al., PODC 2018). However, it has proven much more difficult to design fast MPC algorithms for graph problems in the low-memory MPC model, where the memory-per-machine is restricted to being strongly sublinear in the number of nodes, i.e., O(n^ε) for constant 0 < ε < 1.

In this paper, we present an algorithm for the 2-ruling set problem, running in Õ(log^{1/6} Δ) rounds whp, in the low-memory MPC model. Here Δ is the maximum degree of the graph. We extend this result to β-ruling sets for any integer β > 1. Specifically, we show that a β-ruling set can be computed in the low-memory MPC model with O(nε) memory-per-machine in Õ(β ⋅ log^{1/(2β+1-2)} Δ) rounds, whp. From this it immediately follows that a β-ruling set for β = Ω(logloglog Δ)-ruling set can be computed in just O(β log log n) rounds whp. The above results assume a total memory of Õ(m + n^{1+ε}).

We also present algorithms for β-ruling sets in the low-memory MPC model assuming that the total memory over all machines is restricted to Õ(m). For β > 1, these algorithms are all substantially faster than the Ghaffari-Uitto Õ(√log Δ)-round MIS algorithm in the low-memory MPC model. All our results follow from a Sample-and-Gather Simulation Theorem that shows how random-sampling-based Congest algorithms can be efficiently simulated in the low-memory MPC model. We expect this simulation theorem to be of independent interest beyond the ruling set algorithms derived here. Joint work with Kishore Kothapalli and Sriram Pemmaraju to appear in FSTTCS 2020.
ArXiv
25th of November
14:15 (Helsinki time)
Shaofeng Jiang:
Streaming Algorithms for Geometric Steiner Forest
We consider a natural generalization of the Steiner tree problem, the Steiner forest problem, in the Euclidean plane: the input is a multiset X ⊂ R^2, partitioned into k color classes C_1, C_2, ..., C_k X. The goal is to find a minimum-cost Euclidean graph G such that every color class C_i is connected in G. We study this Steiner forest problem in the streaming setting, where the stream consists of insertions and deletions of points to X. Each input point x\in X arrives with its in [k], and as usual for dynamic geometric streams, the input points are restricted to the discrete grid {0, ..., Δ}^2.

We design a single-pass streaming algorithm that uses poly(k log Δ) space and time, and estimates the cost of an optimal Steiner forest solution within ratio arbitrarily close to the famous Euclidean Steiner ratio alpha_2 (currently 1.1547 < \alpha_2 < 1.214). Our approach relies on a novel combination of streaming techniques, like sampling and linear sketching, with the classical dynamic-programming framework for geometric optimization problems, which usually requires large memory and has so far not been applied in the streaming setting.

Joint work with Artur Czumaj, Robert Krauthgamer and Pavel Veselý.
ArXiv
11th of November
One hour later that usual: 15:15 (Helsinki time)
Przemek Uznański:
Cardinality estimation using Gumbel distribution
Cardinality estimation is the task of approximating the number of distinct elements in a large dataset with possibly repeating elements. LogLog and HyperLogLog (c.f. Durand and Flajolet [ESA 2003], Flajolet et al. [Discrete Math Theor. 2007]) are small space sketching schemes for cardinality estimation, which have both strong theoretical guarantees of performance and are highly effective in practice. This makes them a highly popular solution with many implementations in big-data systems (e.g. Algebird, Apache DataSketches, BigQuery, Presto and Redis). However, despite having simple and elegant formulation, both the analysis of LogLog and HyperLogLog are extremely involved -- spanning over tens of pages of analytic combinatorics and complex function analysis.
We propose a modification to both LogLog and HyperLogLog that replaces discrete geometric distribution with a continuous Gumbel distribution. This leads to a very short, simple and elementary analysis of estimation guarantees, and smoother behavior of the estimator.
ArXiv
28th of October 2020
14:15 (Helsinki time)
Philipp Schneider:
Shortest Paths in the HYBRID Network Model
The HYBRID model, introduced in [Augustine et al., SODA '20], provides a theoretical foundation for networks that allow multiple communication modes. The model follows the principles of synchronous message passing, where nodes are allowed to use two fundamentally different communication modes. First, a local mode where nodes may exchange arbitrary information per round over edges of a local communication graph G (akin to the LOCAL model). Second, a global mode where every node may exchange log n messages of size O(log n) bits per round with arbitrary nodes in the network. The HYBRID model intends to reflect the conditions of many real hybrid networks, where high-bandwidth but inherently local communication is combined with highly flexible global communication with restricted bandwidth.
We explore the power and limitations of the HYBRID model by investigating the complexity of computing shortest paths of the local communication graph G. The aim of the talk is to give an overview of the known techniques for information dissemination in the HYBRID model. Subsequently, we will look into how these techniques can be used to obtain algorithmic upper bounds for various shortest paths problems and how these compare to the known lower bounds. As a sideffect we will also learn how the HYBRID model is related to other models of computation.
ArXiv
21th of October 2020
14:15 (Helsinki time)
Darya Melnyk:
Online Problems with Delays in the Uniform Metric Space
We present tight bounds for the k-server problem with delays in the uniform metric space. The problem is defined on n + k nodes in the uniform metric space which can issue requests over time. These requests can be served directly or with some delay using k servers, by moving a server to the corresponding node with an open request. The task is to find an online algorithm that can serve the requests while minimizing the total moving and delay costs. We first provide a lower bound by showing that the competitive ratio of any deterministic online algorithm cannot be better than (2k + 1) in the clairvoyant setting. We will then show that conservative algorithms (without delay) can be equipped with an accumulative delay function such that all such algorithms become (2k + 1)-competitive in the non-clairvoyant setting. Together, the two bounds establish a tight result for both, the clairvoyant and the non-clairvoyant settings.

We further study a special case of the online Minimum-Cost Perfect Matching with Delays (MPMD) problem introduced by Emek et al. [STOC 2016]. In this problem, a metric space is given and requests arrive at different times at points in this space. The algorithm is allowed to delay the matching of these requests, with the objective to both minimize the sum of distances between matched pairs and the time that passes until a request is matched. We consider the special case of uniform metric spaces with a unit distance between any two points. Our results include a deterministic 3-competitive online algorithm for a uniform metric space consisting of four or fewer points as well as a deterministic 3.5-competitive online algorithm for uniform metric spaces with an arbitrary number of points.
Paper
7th of October 2020
14:15 (Helsinki time)
Aleksander Łukasiewicz:
All-Pairs LCA in DAGs: Breaking through the O(n^2.5) barrier
Let G=(V,E) be an n-vertex directed acyclic graph (DAG). A lowest common ancestor (LCA) of two vertices u and v is a common ancestor w of u and v such that no descendant of w has the same property. In this paper, we consider the problem of computing an LCA, if any, for all pairs of vertices in a DAG. The fastest known algorithms for this problem exploit fast matrix multiplication subroutines and have running times ranging from O(n^2.687) [Bender et al. SODA'01] down to O(n^2.615) [Kowaluk and Lingas~ICALP'05] and O(n^2.569) [Czumaj et al. TCS'07]. Somewhat surprisingly, all those bounds would still be Ω(n^2.5) even if matrix multiplication could be solved optimally (i.e., ω=2). This appears to be an inherent barrier for all the currently known approaches, which raises the natural question on whether one could break through the O(n^2.5) barrier for this problem.
In this paper, we answer this question affirmatively: in particular, we present an O(n^2.447) (O(n^7/3) for ω=2) algorithm for finding an LCA for all pairs of vertices in a DAG, which represents the first improvement on the running times for this problem in the last 13 years. A key tool in our approach is a fast algorithm to partition the vertex set of the transitive closure of G into a collection of O(ℓ) chains and O(n/ℓ) antichains, for a given parameter ℓ. As usual, a chain is a path while an antichain is an independent set. We then find, for all pairs of vertices, a candidate} LCA among the chain and antichain vertices, separately. The first set is obtained via a reduction to min-max matrix multiplication. The computation of the second set can be reduced to Boolean matrix multiplication similarly to previous results on this problem. We finally combine the two solutions together in a careful (non-obvious) manner.
To appear in SODA 2021.
ArXiv
30th September 2020
14:15 (Helsinki time)
Julian Portmann:
Tight Bounds for Deterministic High-Dimensional Grid Exploration
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are required to explore the grid, or equivalently, find a hidden treasure in the grid, is fully understood in both the synchronous and the semi-synchronous setting. For higher dimensions, Dobrev, Narayanan, Opatrny, and Pankratov [ICALP'19] showed very recently that, surprisingly, a (small) constant number of agents suffices to find the treasure, independent of the number of dimensions, thereby disproving a conjecture by Cohen, Emek, Louidor, and Uitto [SODA'17]. Dobrev et al. left as an open question whether their bounds on the number of agents can be improved. We answer this question in the affirmative for deterministic finite automata: we show that 3 synchronous and 4 semi-synchronous agents suffice to explore an n-dimensional grid for any constant n. The bounds are optimal and notably, the matching lower bounds already hold in the 2-dimensional case.
Our techniques can also be used to make progress on other open questions asked by Dobrev et al.: we prove that 4 synchronous and 5 semi-synchronous agents suffice for polynomial-time exploration, and we show that, under a natural assumption, 3 synchronous and 4 semi-synchronous agents suffice to explore unoriented grids of arbitrary dimension (which, again, is tight).
ArXiv
16th September 2020
14:15 (Helsinki time)
Janne Korhonen:
Input-dynamic distributed graph algorithms for congested networks
Consider a distributed system, where the topology of the communication network remains fixed, but local inputs given to nodes may change over time. In this work, we explore the following question: if some of the local inputs change, can an existing solution be updated efficiently, in a dynamic and distributed manner? To address this question, we define the batch dynamic CONGEST model, where the communication network G=(V,E) remains fixed and a dynamic edge labelling defines the problem input. The task is to maintain a solution to a graph problem on the labeled graph under batch changes. We investigate, when a batch of α edge label changes arrive,
— how much time as a function of α we need to update an existing solution, and
— how much information the nodes have to keep in local memory between batches in order to update the solution quickly.
We give a general picture of the complexity landscape in this model, including a general framework for lower bounds. In particular, we prove non-trivial upper bounds for two selected, contrasting problems: maintaining a minimum spanning tree and detecting cliques.
ArXiv
9nd September 2020
14:15 (Helsinki time)
Yannic Maus:
Distributed Graph Coloring: Linial for Lists
Linial's famous color reduction algorithm reduces a given m-coloring of a graph with maximum degree Δ to a O(Δ² log m)-coloring, in a single round in the LOCAL model. We show a similar result when nodes are restricted to choose their color from a list of allowed colors: given an m-coloring in a directed graph of maximum outdegree β, if every node has a list of size Ω(β² (log β + log log m + log log |C|)) from a color space C then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial's color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring algorithm. As a corollary, we improve the state-of-the-art truly local (deg+1)-list coloring algorithm from Barenboim et al. [PODC'18] by slightly reducing the runtime to O(sqrt(Δ log Δ) + log* n) and significantly reducing the message size (from huge to roughly Δ). Our techniques are inspired by the local conflict coloring framework of Fraigniaud et al. [FOCS'16]. ArXiv
26th August 2020
14:15 (Helsinki time)
Ebrahim Ghorbani:
Spectral gap of regular graphs and a conjecture by Aldous-Fill on the relaxation time of the random walk
Aldous and Fill conjectured that the maximum relaxation time for the random walk on a connected regular graph with n vertices is (1+o(1)) \frac{3n^2}{2\pi^2}. This conjecture can be rephrased in terms of the spectral gap as follows: the spectral gap (algebraic connectivity) of a connected k-regular graph on n vertices is at least (1+o(1))\frac{2k\pi^2}{3n^2}, and the bound is attained for at least one value of k. Brand, Guiduli, and Imrich determined the structure of connected cubic graphs on n vertices with minimum spectral gap. We investigate the structure of quartic (i.e.~4-regular) graphs with the minimum spectral gap among all connected quartic graphs. We show that they must have a path-like structure built from specific blocks. Based on these results, we prove the Aldous--Fill conjecture follows for k=3 and 4. This talk is based on joint works with M. Abdi and W. Imrich.
19th August 2020
14:15 (Helsinki time)
Klaus-Tycho Förster:
On the Feasibility of Perfect Resilience with Local Fast Failover
In order to provide a high resilience and to react quickly to link failures, modern computer networks support fully decentralized flow rerouting, also known as local fast failover. In a nutshell, the task of a local fast failover algorithm is to pre-define fast failover rules for each node using locally available information only. These rules determine for each incoming link from which a packet may arrive and the set of local link failures (i.e., the failed links incident to a node), on which outgoing link a packet should be forwarded. Ideally, such a local fast failover algorithm provides a perfect resilience deterministically: a packet emitted from any source can reach any target, as long as the underlying network remains connected. Feigenbaum et al. showed that it is not always possible to provide perfect resilience and showed how to tolerate a single failure in any network. Interestingly, not much more is known currently about the feasibility of perfect resilience.

This paper revisits perfect resilience with local fast failover, both in a model where the source can and cannot be used for forwarding decisions. We first derive several fairly general impossibility results: By establishing a connection between graph minors and resilience, we prove that it is impossible to achieve perfect resilience on any non-planar graph; furthermore, while planarity is necessary, it is also not sufficient for perfect resilience. On the positive side, we show that graph families which are closed under the subdivision of links, can allow for simple and efficient failover algorithms which simply skip failed links. We demonstrate this technique by deriving perfect resilience for outerplanar graphs and related scenarios, as well as for scenarios where the source and target are topologically close after failures.
Paper
12th August 2020
14:15 (Helsinki time)
Chris Brzuska:
On Building Fine-Grained One-Way Functions from Strong Average-Case Hardness
Constructing one-way function from average-case hardness is a long-standing open problem A positive result would exclude Pessiland (Impagliazzo '95) and establish a highly desirable win-win situation:
Either (symmetric) cryptography exists unconditionally, enabling many of the important primitives which are used to secure our communications, or all NP problems can be solved efficiently on average, which would be a revolution in algorithms. Motivated by the interest of establishing such a win-win result and the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate win-win results. Specifically, we study the following type of win-win results: either there are fine-grained one-way functions (FGOWF), which relax the standard notion of a one-way function by requiring only a fixed polynomial gap (as opposed to superpolynomial) between the running time of the function and the running time of an inverter, or nontrivial speedups can be obtained for all NP problems on average. We obtain three main results:

- We introduce the random language model (RLM), which captures idealized average-case hard languages, analogous to how the random oracle model captures idealized one-way functions. We provide a construction of a FGOWF (with quadratic hardness gap) and prove its security in the RLM. This rules out an idealized version of Pessiland, where ideally hard languages would exist yet even weak forms of cryptography would fail.

- On the negative side, we prove a strong oracle separation: we show that there is no black-box proof that either FGOWF exist, or non-trivial speedup can be obtained for all NP languages on average (i.e., there is no exponentially average-case hard NP languages).

- We provide a second strong negative result for an even weaker candidate win-win result: there is no black-box proof that either FGOWF exist, or non-trivial speedups can be obtained for all NP languages on average when amortizing over many instances (i.e., there is no exponentially average-case hard NP languages whose hardness amplifies optimally through parallel repetitions). This separation forms the core technical contribution of our work.

Our results lay the foundations for a program towards building fine-grained one-way functions from strong forms of average-case hardness, following the template of constructions in the random language model. We provide a preliminary investigation of this program, showing black-box barriers toward instantiating our idealized constructions from natural hardness properties.

Joint work with Geoffroy Couteau.
29th July 2020
14:15 (Helsinki time)
Davin Choo:
k-means++: few more steps yield constant approximation
The k-means++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a state-of-the-art algorithm for solving the k-means clustering problem and is known to give an O(log k)-approximation in expectation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting k-means++ with O(k log log k) local search steps to yield a constant approximation (in expectation) to the k-means clustering problem. In this paper, we improve their analysis to show that, for any arbitrarily small constant $\eps > 0$, with only $\eps k$ additional local search steps, one can achieve a constant approximation guarantee (with high probability in k), resolving an open problem in their paper. Paper
22nd July 2020
14:15 (Helsinki time)
Yuval Efron:
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
By far the most fruitful technique for showing lower bounds for the CONGEST model is reductions to two-party communication complexity. This technique has yielded nearly tight results for various fundamental problems such as distance computations, minimum spanning tree, minimum vertex cover, and more. In this work, we take this technique a step further, and we introduce a framework of reductions to t-party communication complexity, for every t≥2. Our framework enables us to show improved hardness results for maximum independent set. Recently, Bachrach et al.[PODC 2019] used the two-party framework to show hardness of approximation for maximum independent set. They show that finding a (5/6+ϵ)-approximation requires Ω(n/log6n) rounds, and finding a (7/8+ϵ)-approximation requires Ω(n2/log7n) rounds, in the CONGEST model where n in the number of nodes in the network. We improve the results of Bachrach et al. by using reductions to multi-party communication complexity. Our results:
(1) Any algorithm that finds a (1/2+ϵ)-approximation for maximum independent set in the CONGEST model requires Ω(n/log3n) rounds.
(2) Any algorithm that finds a (3/4+ϵ)-approximation for maximum independent set in the CONGEST model requires Ω(n2/log3n) rounds.
Paper
15th July 2020
14:15 (Helsinki time)
Yi-Jun Chang:
Simple Contention Resolution via Multiplicative Weight Updates
We consider the classic contention resolution problem, in which devices conspire to share some common resource, for which they each need temporary and exclusive access. To ground the discussion, suppose (identical) devices wake up at various times, and must send a single packet over a shared multiple-access channel. In each time step they may attempt to send their packet; they receive ternary feedback {0,1,2^+} from the channel, 0 indicating silence (no one attempted transmission), 1 indicating success (one device successfully transmitted), and 2^+ indicating noise. We prove that a simple strategy suffices to achieve a channel utilization rate of 1/e-O(epsilon), for any epsilon > 0. In each step, device i attempts to send its packet with probability p_i, then applies a rudimentary multiplicative weight-type update to p_i. p_i ← { p_i * e^{epsilon} upon hearing silence (0), p_i upon hearing success (1), p_i * e^{-epsilon/(e-2)} upon hearing noise (2^+) }. This scheme works well even if the introduction of devices/packets is adversarial, and even if the adversary can jam time slots (make noise) at will. We prove that if the adversary jams J time slots, then this scheme will achieve channel utilization 1/e-epsilon, excluding O(J) wasted slots. Results similar to these (Bender, Fineman, Gilbert, Young, SODA 2016) were already achieved, but with a lower constant efficiency (less than 0.05) and a more complex algorithm. Paper
8th July 2020
14:15 (Helsinki time)
Diksha Gupta:
Sybil Defense in the Presence of Churn Using Resource Burning
In this talk, I will begin by discussing a recent result for defending against Sybil attacks in dynamic permissionless systems, in the presence of a computationally bounded adversary - TOtal Good COMputation (ToGCom). This technique guarantees a majority of honest identities (IDs) at all times, at a computational cost to the protocol that is comparable to that of the attacker. Next, I will talk about the concept of resource burning - the verifiable consumption of resources. This resource does not necessarily need to be computational power, but can also be communication capacity, computer memory, and human effort, subject to some constraints. Using this insight, I will conclude with a generalizing of our Sybil defense techniques to a variety of systems with churn, in the presence of a resource-bounded adversary.
1st July 2020
14:15 (Helsinki time)
Sebastian Brandt:
Lower Bounds for Ruling Sets in the LOCAL Model
Given a graph G = (V,E), an (a,b)-ruling set is a subset S of V such that the distance between any two vertices in S is at least a, and the distance between any vertex in V and the closest vertex in S is at most b. Ruling sets are a generalization of maximal independent sets (which are (2,1)-ruling sets) and constitute an important building block of many distributed algorithms. The recent breakthrough on network decompositions by Rozhon and Ghaffari [STOC'20] implies that, in the distributed LOCAL model, ruling sets can be computed deterministically in polylogarithmic time, for a wide range of parameters a, b.

In this talk, we present polylogarithmic lower bounds for the deterministic computation of ruling sets, and Omega(poly(log log n)) lower bounds for the randomized computation of ruling sets, both in the LOCAL model, improving on the previously best known lower bounds of Omega(log*n)) by Linial [FOCS'87] and Naor [J.Disc.Math.'91]. In the special case of maximal independent sets, such lower bounds were already known; however, our lower bounds are the first (beyond Omega(log*n)) that are also applicable on trees.
Paper
17th June 2020
14:15 (Helsinki time)
Frederik Mallman-Trenn:
Finding the best papers with noisy reviews
Say you are tasked to find the best 150 papers among more than 550 papers. You can ask people to review a given paper by either asking
1) Is paper A better than paper B
or
2) What’s the score of paper A?
The problem is that each review returns an incorrect response with a small probability, say 2/3. How can you assign reviews so that you the total number of queries is small and the number of review rounds is small?
Paper
10th June 2020
14:15 (Helsinki time)
Joachim Spoerhase:
Approximation Algorithms for some Submodular and Graph-based Optimization Problems
In this talk, I will give an overview over three recent results on approximation algorithms for discrete optimization problems. The first result concerns optimizing a monotone submodular function with respect to an arbitrary (constant) number of packing and covering constraints. We give a randomized polynomial-time approximation algorithm that is essentially tight with respect to approximation ratio, running time, and constraint violation. The algorithm is based on rounding a multi-linear relaxation of the problem. We also discuss special cases where we can give *deterministic* algorithms based on a novel combinatorial approach. The second set of results concerns optimization problems for graphs. We will briefly look at a polynomial-time approximation scheme (PTAS) for Steiner tree on map graphs, which generalizes a known PTAS planar (edge-weighted) Steiner tree, and which is motivated by the study of planar node-weighted Steiner trees. We will also touch upon a result for the sparsest cut problem in tree-width bounded graphs.

REMARK: This talk is given as a memorial for Sumedha Uniyal who was a postdoc at Aalto for 3 years until she passed away on February 19, 2020. I will give an overview over our three joint results. Additional contributors include Jaroslaw Byrka (Wroclaw), Parinya Chalermsook (Aalto), Mateusz Lewandowski (Wroclaw), Syed Mohammad Meesum (Wroclaw), Eyal Mizrachi (Technion), Matthias Mnich (TU Hamburg) Roy Schwartz (Technion), Daniel Vaz (TU Munich)
3rd June 2020
14:15 (Helsinki time)
Parinya Chalermsook:
Some New Algorithmic Min-Max Relations via Local Search
The study of min-max relations has been a cornerstone in combinatorial optimization. Classic examples include, for instance, LP duality relations, Tutte-Berge formula, and the notion of perfect graphs. These relations have yielded many ground-breaking algorithmic results. Algorithmic uses of these bounds often involve two steps: (1) Prove a non-constructive bound and (2) Use another technique (e.g. convex programs) to turn the first step algorithmic. In this talk, I will report our recent use of local search arguments to derive two new algorithmic min-max relations in one go. In these results, a bound is proved by showing that a locally optimal solution must satisfy such bound, therefore yielding immediately an efficient algorithm.

REMARK: This talk is given as a memorial for Sumedha Uniyal who was a postdoc at Aalto for 3 years until she passed away on February 19, 2020. She played a central role in this project. Additional contributors include Samir Khuller (Northwestern), Andreas Schmid (Aalto), and Pattara Sukprasert (Northwestern).
27th May 2020
14:15 (Helsinki time)
Krzysztof Nowicki:
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2-out edge sampling from each vertex rather than the standard uniform edge sampling. Our new approach yields better algorithms for sequential, distributed, and parallel models of computation. Paper
20th May 2020
15:15 (Helsinki time, one hour later than usually!)
Jan Studený:
On the Hardness of Classifying Distributed Complexity of Graph Problems on Paths, Cycles, and Trees
Given the description of a locally checkable graph problem Π for paths or cycles or trees, find out how hard is to determine what the distributed complexity of solving Π in the usual LOCAL model of distributed computing. In this talk I will present our results on answering this question for paths and cycles and discuss the case of trees. Paper
13th May 2020
14:15 (Helsinki time)
Manuela Fischer:
Local Glauber Dynamics
Sampling constitutes an important tool in a variety of areas: from machine learning and combinatorial optimization to computational physics and biology. A central class of sampling algorithms is the Markov Chain Monte Carlo method, based on the construction of a Markov chain with the desired sampling distribution as its stationary distribution. Many of the traditional Markov chains, such as the Glauber dynamics, do not scale well with increasing dimension. To address this shortcoming, we propose a simple local update rule based on the Glauber dynamics that leads to efficient parallel and distributed algorithms for sampling from Gibbs distributions. Concretely, we present a Markov chain that mixes in O(logn) rounds when Dobrushin's condition for the Gibbs distribution is satisfied. This improves over the LubyGlauber algorithm by Feng, Sun, and Yin [PODC'17], which needs O(Δ log n) rounds, and their LocalMetropolis algorithm, which converges in O(log n) rounds but requires a considerably stronger mixing condition. Here, n denotes the number of nodes in the graphical model inducing the Gibbs distribution, and Δ its maximum degree. In particular, our method can sample a uniform proper coloring with α Δ colors in O(log n) rounds for any α > 2, which almost matches the threshold of the sequential Glauber dynamics and improves on the α > 2+sqrt(2)- threshold of Feng et al. Paper
6th May 2020
14:15 (Helsinki time)
Jesper Nederlof:
Bipartite TSP in O(1.9999^n) Time, Assuming Quadratic Time Matrix Multiplication
The symmetric traveling salesman problem (TSP) is the problem of finding the shortest Hamiltonian cycle in an edge-weighted undirected graph. In 1962 Bellman, and independently Held and Karp, showed that TSP instances with n cities can be solved in O(n^2*2^n) time. Since then it has been a notorious problem to improve the runtime to O((2-eps)^n) for some constant eps >0. In this work we establish the following progress: If (s x s)-matrices can be multiplied in s^{2+o(1)} time, than all instances of TSP in bipartite graphs can be solved in O(1.9999^n) time by a randomized algorithm with constant error probability. We also indicate how our methods may be useful to solve TSP in non-bipartite graphs.
On a high level, our approach is via a new problem called the MINHAMPAIR problem: Given two families of weighted perfect matchings, find a combination of minimum weight that forms a Hamiltonian cycle. As our main technical contribution, we give a fast algorithm for MINHAMPAIR based on a new sparse cut-based factorization of the `matchings connectivity matrix', introduced by Cygan et al. [JACM'18].
29th April 2020
14:15 (Helsinki time)
Sorrachai Yingchareonthawornchai:
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Consider the following "local" cut-detection problem in a directed graph: We are given a seed vertex x and need to remove at most k edges so that at most ν edges can be reached from x (a "local" cut) or output ⊥ to indicate that no such cut exists. If we are given query access to the input graph, then this problem can in principle be solved without reading the whole graph and with query complexity depending on k and ν. In this talk, I will present a simple randomized algorithm spending O(νk^2) time and O(kν) queries for the slight variant of the above problem, improving in particular a previous time bound of O(k^O(k) ν) by Chechik et al. [SODA '17]. I will then present two key applications of the local cut algorithm. The first application is a fast randomized algorithm for the classic k-vertex connectivity problem that takes near-linear time when k = O(polylog(n)). Second is property testing algorithms for k-edge and -vertex connectivity with query complexities that are near-linear in k, exponentially improving the state-of-the-art. This resolves two open problems, one by Goldreich and Ron [STOC '97] and one by Orenstein and Ron [Theor. Comput Sci. '11]. Paper
22th April 2020
15:15 (Helsinki time
Václav Rozhoň:
Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization
We present a simple polylogarithmic-time deterministic distributed algorithm for network decomposition. This improves on a celebrated 2^O(sqrt(log n))-time algorithm of Panconesi and Srinivasan [STOC'92] and settles a long-standing question in distributed graph algorithms. It also leads to the first polylogarithmic-time deterministic distributed algorithms for numerous other problems, hence resolving several well-known open problems, including Linial's question about the deterministic complexity of maximal independent set [FOCS'87; SICOMP'92]. By known connections, our result leads also to substantially faster randomized distributed algorithms for a number of well-studied problems including (Delta+1)-coloring, maximal independent set, and Lovász Local Lemma, as well as massively parallel algorithms for (Delta+1)-coloring. Paper
15th April 2020
14:15 (Helsinki time
Przemek Uznański:
Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. An important class of distance labeling schemes is that of hub labelings, where a node v∈G stores its distance to the so-called hubs S(v)⊆V, chosen so that for any u,v∈V there is w∈S(u)∩S(v) belonging to some shortest uv path. Notice that for most existing graph classes, the best distance labelling constructions existing use at some point a hub labeling scheme at least as a key building block. Our interest lies in hub labelings of sparse graphs, i.e., those with |E(G)|=O(n), for which we show a lowerbound of n/2^O(√logn) for the average size of the hubsets. Additionally, we show a hub-labeling construction for sparse graphs of average size O(n/RS(n)^c) for some 0 < c < 1, where RS(n) is the so-called Ruzsa-Szemerédi function, linked to structure of induced matchings in dense graphs. This implies that further improving the lower bound on hub labeling size to n/2^(logn)^o(1) would require a breakthrough in the study of lower bounds on RS(n), which have resisted substantial improvement in the last 70 years. For general distance labeling of sparse graphs, we show a lowerbound of 1/2O(√logn) * SumIndex(n), where SumIndex(n) is the communication complexity of the Sum-Index problem over Z_n. Our results suggest that the best achievable hub-label size and distance-label size in sparse graphs may be Θ(n/2^(log n)^c) for some 0 < c < 1. Paper
8th April 2020
14:15 (Helsinki time
Alex Jung:
On the Duality between Network Flows and Network Lasso
Many applications generate data with an intrinsic network structure such as time series data, image data or social network data. The network Lasso (nLasso) has been proposed recently as a method for joint clustering and optimization of machine learning models for networked data. The nLasso extends the Lasso from sparse linear models to clustered graph signals. This paper explores the duality of nLasso and network flow optimization. We show that, in a very precise sense, nLasso is equivalent to a minimum-cost flow problem on the data network structure. Our main technical result is a concise characterization of nLasso solutions via existence of certain network flows. The main conceptual result is a useful link between nLasso methods and basic graph algorithms such as clustering or maximum flow. Paper
1st April 2020
14:15 (Helsinki time)
Petteri Kaski:
Probabilistic Tensors and Opportunistic Boolean Matrix Multiplication
We introduce probabilistic extensions of classical deterministic measures of algebraic complexity of a tensor, such as the rank and the border rank. We show that these probabilistic extensions satisfy various natural and algorithmically serendipitous properties, such as submultiplicativity under taking of Kronecker products. Furthermore, the probabilistic extensions enable strictly lower rank over their deterministic counterparts for specific tensors of interest, starting from the tensor <2,2,2> that represents 2-by-2 matrix multiplication. By submultiplicativity, this leads immediately to novel randomized algorithm designs, such as algorithms for Boolean matrix multiplication as well as detecting and estimating the number of triangles and other subgraphs in graphs. Paper
25th March 2020
14:15 (Helsinki time)
Jukka Suomela:
Foundations of Distributed Computing in the 2020s
In this talk I will review some major advances in the theory of distributed computing in the past decade and discuss key research challenges for the 2020s, with the main focus on distributed graph algorithms. I will present promising new approaches for doing research in the field, and I will also highlight examples of seemingly elementary questions that are still beyond the reach of our current techniques. Slides