Date and Time  Speaker and Title  Abstract  Reference 

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 firstclass citizens. Background: Metafinite model theory (Grädel & Gurevich 1998) generalizes the approach of finite model theory by shifting to twosorted 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 Rstructures. BlumShubSmale 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 BSSmachiness in nondeterminitic 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 secondorder logic over Rstructures 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 builtup 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 realweighted distributions over firstorder assignments. Hence, it turns out, that the descriptive complexity of related logics lie in the realm of BSSmachines. For pinpointing the exact complexity of logics in the probabilistic team semantics setting, we introduced a novel restricted variant of BSS machines, coined "separatebranching BSSmachines" or SBSSmachines. This led to various connections between logics using probabilistic team semantics, complexity classes defined via SBSSmachines, complexity classes defined via Turing machines, and restrictions of the variant of existential secondorder 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 neuralinspired 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 longstanding \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 messageoptimal 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., 11/n^c for constant c. Our results demonstrate that leader election can be solved in a simultaneously message and timeefficient 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: SampleandGather: Fast Ruling Set Algorithms in the LowMemory MPC Model 
Motivated by recent progress on symmetry breaking problems such as maximal independent set (MIS) and maximal matching in the lowmemory Massively Parallel Computation (MPC) model (e.g., Behnezhad et al. PODC 2019; GhaffariUitto SODA 2019), we investigate the complexity of ruling set problems in this model. The MPC model has become very popular as a model for largescale distributed computing and it comes with the constraint that the memorypermachine is strongly sublinear in the input size. For graph problems, extremely fast MPC algorithms have been designed assuming Õ(n) memorypermachine, 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 lowmemory MPC model, where the memorypermachine 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 2ruling set problem, running in Õ(log^{1/6} Δ) rounds whp, in the lowmemory 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 lowmemory MPC model with O(nε) memorypermachine in Õ(β ⋅ log^{1/(2β+12)} Δ) 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 lowmemory MPC model assuming that the total memory over all machines is restricted to Õ(m). For β > 1, these algorithms are all substantially faster than the GhaffariUitto Õ(√log Δ)round MIS algorithm in the lowmemory MPC model. All our results follow from a SampleandGather Simulation Theorem that shows how randomsamplingbased Congest algorithms can be efficiently simulated in the lowmemory 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 minimumcost 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 singlepass 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 dynamicprogramming 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 bigdata 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 highbandwidth 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 kserver 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 nonclairvoyant setting. Together, the two
bounds establish a tight result for both, the clairvoyant and the
nonclairvoyant settings. We further study a special case of the online MinimumCost 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 3competitive online algorithm for a uniform metric space consisting of four or fewer points as well as a deterministic 3.5competitive online algorithm for uniform metric spaces with an arbitrary number of points. 
Paper 
7th of October 2020 14:15 (Helsinki time) 
Aleksander Łukasiewicz: AllPairs LCA in DAGs: Breaking through the O(n^2.5) barrier 
Let G=(V,E) be an nvertex 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 minmax 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 (nonobvious) manner. To appear in SODA 2021. 
ArXiv 
30th September 2020 14:15 (Helsinki time) 
Julian Portmann: Tight Bounds for Deterministic HighDimensional Grid Exploration 
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2dimensional 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 semisynchronous 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 semisynchronous agents suffice to explore an ndimensional grid for any constant n. The bounds are optimal and notably, the matching lower bounds already hold in the 2dimensional 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 semisynchronous agents suffice for polynomialtime exploration, and we show that, under a natural assumption, 3 synchronous and 4 semisynchronous agents suffice to explore unoriented grids of arbitrary dimension (which, again, is tight). 
ArXiv 
16th September 2020 14:15 (Helsinki time) 
Janne Korhonen: Inputdynamic 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 nontrivial 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 mcoloring 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 mcoloring 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 stateoftheart 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 AldousFill 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 kregular 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.~4regular) graphs with the minimum spectral gap among all connected quartic graphs. We show that they must have a pathlike structure built from specific blocks. Based on these results, we prove the AldousFill 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) 
KlausTycho 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 predefine 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 nonplanar 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 FineGrained OneWay Functions from Strong AverageCase Hardness 
Constructing oneway function from averagecase hardness is a longstanding open problem
A positive result would exclude Pessiland (Impagliazzo '95) and establish a highly desirable winwin 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 winwin result and the lack of progress on this seemingly very hard question, we initiate the investigation of weaker yet meaningful candidate winwin results. Specifically, we study the following type of winwin results: either there are finegrained oneway functions (FGOWF), which relax the standard notion of a oneway 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 averagecase hard languages, analogous to how the random oracle model captures idealized oneway 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 blackbox proof that either FGOWF exist, or nontrivial speedup can be obtained for all NP languages on average (i.e., there is no exponentially averagecase hard NP languages).  We provide a second strong negative result for an even weaker candidate winwin result: there is no blackbox proof that either FGOWF exist, or nontrivial speedups can be obtained for all NP languages on average when amortizing over many instances (i.e., there is no exponentially averagecase 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 finegrained oneway functions from strong forms of averagecase hardness, following the template of constructions in the random language model. We provide a preliminary investigation of this program, showing blackbox barriers toward instantiating our idealized constructions from natural hardness properties. Joint work with Geoffroy Couteau. 

29th July 2020 14:15 (Helsinki time) 
Davin Choo: kmeans++: few more steps yield constant approximation 
The kmeans++ algorithm of Arthur and Vassilvitskii (SODA 2007) is a stateoftheart algorithm for solving the kmeans clustering problem and is known to give an O(log k)approximation in expectation. Recently, Lattanzi and Sohler (ICML 2019) proposed augmenting kmeans++ with O(k log log k) local search steps to yield a constant approximation (in expectation) to the kmeans 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 twoparty 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 tparty 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 twoparty 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 multiparty 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) 
YiJun 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 multipleaccess 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/eO(epsilon), for any epsilon > 0. In each step, device i attempts to send its packet with probability p_i, then applies a rudimentary multiplicative weighttype update to p_i. p_i ← { p_i * e^{epsilon} upon hearing silence (0), p_i upon hearing success (1), p_i * e^{epsilon/(e2)} 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/eepsilon, 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 resourcebounded 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 MallmanTrenn: 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 Graphbased 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 polynomialtime approximation algorithm that is essentially tight with respect to approximation ratio, running time, and constraint violation. The algorithm is based on rounding a multilinear 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 polynomialtime approximation scheme (PTAS) for Steiner tree on map graphs, which generalizes a known PTAS planar (edgeweighted) Steiner tree, and which is motivated by the study of planar nodeweighted Steiner trees. We will also touch upon a result for the sparsest cut problem in treewidth 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 MinMax Relations via Local Search 
The study of minmax relations has been a cornerstone in combinatorial optimization. Classic examples include, for instance, LP duality relations, TutteBerge formula, and the notion of perfect graphs. These relations have yielded many groundbreaking algorithmic results. Algorithmic uses of these bounds often involve two steps: (1) Prove a nonconstructive 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 minmax 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 2Out Contractions 
We provide a simple new randomized contraction approach to the global minimum cut problem for simple undirected graphs. The contractions exploit 2out 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 edgeweighted 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((2eps)^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 nonbipartite 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 cutbased 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 NearLinear Time and Queries via Fast Local Cut Algorithms 
Consider the following "local" cutdetection 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 kvertex connectivity problem that takes nearlinear time when k = O(polylog(n)). Second is property testing algorithms for kedge and vertex connectivity with query complexities that are nearlinear in k, exponentially improving the stateoftheart. 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ň: PolylogarithmicTime Deterministic Network Decomposition and Distributed Derandomization 
We present a simple polylogarithmictime 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 longstanding question in distributed graph algorithms. It also leads to the first polylogarithmictime deterministic distributed algorithms for numerous other problems, hence resolving several wellknown 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 wellstudied 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 bitlabels 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 socalled 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 hublabeling construction for sparse graphs of average size O(n/RS(n)^c) for some 0 < c < 1, where RS(n) is the socalled RuzsaSzemeré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 SumIndex problem over Z_n. Our results suggest that the best achievable hublabel size and distancelabel 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 minimumcost 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 2by2 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 