Manuela Fischer

SODA Conference 2023 Conference Paper

Fast Distributed Brooks' Theorem

• Manuela Fischer
• Magnús M. Halldórsson
• Yannic Maus

STOC Conference 2022 Conference Paper

Deterministic (1+ ε )-approximate maximum matching with poly(1/ ε ) passes in the semi-streaming model and beyond

• Manuela Fischer
• Slobodan Mitrovic
• Jara Uitto

We present a deterministic (1+ε)-approximate maximum matching algorithm in poly (1/ε) passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on 1/ε. Our algorithm exponentially improves on the well-known randomized (1/ε) O (1/ε) -pass algorithm from the seminal work by McGregor [APPROX05], the recent deterministic algorithm by Tirodkar with the same pass complexity [FSTTCS18]. Up to polynomial factors in 1/ε, our work matches the state-of-the-art deterministic (log n / loglog n ) · (1/ε)-pass algorithm by Ahn and Guha [TOPC18], that is allowed a dependence on the number of nodes n . Our result also makes progress on the Open Problem 60 at sublinear.info. Moreover, we design a general framework that simulates our approach for the streaming setting in other models of computation. This framework requires access to an algorithm computing a maximal matching and an algorithm for processing disjoint ( 1 / ε)-size connected components. Instantiating our framework in CONGEST yields a (log n , 1/ε) round algorithm for computing (1+ε)-approximate maximum matching. In terms of the dependence on 1/ε, this result improves exponentially state-of-the-art result by Lotker, Patt-Shamir, and Pettie [LPSP15]. Our framework leads to the same quality of improvement in the context of the Massively Parallel Computation model as well.

TCS Journal 2021 Journal Article

Breaking the linear-memory barrier in MPC: Fast MIS on trees with strongly sublinear memory

• Sebastian Brandt
• Manuela Fischer
• Jara Uitto

Recently, studying fundamental graph problems in the Massively Parallel Computation ( MPC ) framework, inspired by the MapReduce paradigm, has gained a lot of attention. An assumption common to a vast majority of approaches is to allow Ω ˜ ( n ) memory per machine, where n is the number of nodes in the graph and Ω ˜ hides polylogarithmic factors. However, as pointed out by Karloff et al. [SODA'10] and Czumaj et al. [STOC'18], it might be unrealistic for a single machine to have linear or only slightly sublinear memory. In this paper, we thus study a more practical variant of the MPC model which only requires substantially sublinear or even subpolynomial memory per machine. In contrast to the linear-memory MPC model and also to streaming algorithms, in this low-memory MPC setting, a single machine will only see a small number of nodes in the graph. We introduce a new and strikingly simple technique to cope with this imposed locality. In particular, we show that the Maximal Independent Set ( MIS ) problem can be solved efficiently, that is, in O ( log 3 ⁡ log ⁡ n ) rounds, when the input graph is a tree. This constitutes an almost exponential speed-up over the low-memory MPC algorithm in O ˜ ( log ⁡ n ) rounds in a concurrent work by Ghaffari and Uitto [SODA'19] and substantially reduces the local memory from Ω ˜ ( n ) required by the recent O ( log ⁡ log ⁡ n ) -round MIS algorithm of Ghaffari et al. [PODC'18] to n ε for any ε > 0, without incurring a significant loss in the round complexity. Moreover, it demonstrates how to make use of the all-to-all communication in the MPC model to almost exponentially improve on the corresponding bound in the LOCAL and PRAM models by Lenzen and Wattenhofer [PODC'11].

AAAI Conference 2021 Conference Paper

Extreme k-Center Clustering

• MohammadHossein Bateni
• Hossein Esfandiari
• Manuela Fischer
• Vahab Mirrokni

Metric clustering is a fundamental primitive in machine learning with several applications for mining massive datasets. An important example of metric clustering is the k-center problem. While this problem has been extensively studied in distributed settings, all previous algorithms use Ω(k) space per machine and Ω(nk) total work. In this paper, we develop the first highly scalable approximation algorithm for k-center clustering, with e O(nε ) space per machine and e O(n1+ ) total work, for arbitrary small constant ε. It produces an O(log log log n)approximate solution with k(1+o(1)) centers in O(log log n) rounds of computation.

SODA Conference 2018 Conference Paper

Tight Analysis of Parallel Randomized Greedy MIS

• Manuela Fischer
• Andreas Noever

We provide a tight analysis which settles the round complexity of the well-studied parallel randomized greedy MIS algorithm, thus answering the main open question of Blelloch, Fineman, and Shun [SPAA’12]. The parallel/distributed randomized greedy Maximal Independent Set (MIS) algorithm works as follows. An order of the vertices is chosen uniformly at random. Then, in each round, all vertices that appear before their neighbors in the order are added to the independent set and removed from the graph along with their neighbors. The main question of interest is the number of rounds it takes until the graph is empty. This algorithm has been studied since 1987, initiated by Coppersmith, Raghavan, and Tompa [FOCS’87], and the previously best known bounds were O (log n ) rounds in expectation for Erdős-Rényi random graphs by Calkin and Frieze [Random Struc. & Alg. ’90] and O (log 2 n ) rounds with high probability for general graphs by Blelloch, Fineman, and Shun [SPAA’12]. We prove a high probability upper bound of O (log n ) on the round complexity of this algorithm in general graphs, and that this bound is tight. This also shows that parallel randomized greedy MIS is as fast as the celebrated algorithm of Luby [STOC’85, JALG’86].

FOCS Conference 2017 Conference Paper

Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching

• Manuela Fischer
• Mohsen Ghaffari 0001
• Fabian Kuhn

We present a deterministic distributed algorithm that computes a (2Δ-1)-edge-coloring, or even list-edge-coloring, in any n-node graph with maximum degree Δ, in O(log 8 Δ·log n) rounds. This answers one of the long-standing open questions of distributed graph algorithms} from the late 1980s, which asked for a polylogarithmic-time algorithm. See, e. g. , Open Problem 4 in the Distributed Graph Coloring book of Barenboim and Elkin. The previous best round complexities were 2 O(√(log n) by Panconesi and Srinivasan [STOC'92] and Õ(√(Δ)) + O(log* n) by Fraigniaud, Heinrich, and Kosowski [FOCS'16]. A corollary of our deterministic list-edge-coloring also improves the randomized complexity of (2Δ-1)-edge-coloring to poly(log log n) rounds. The key technical ingredient is a deterministic distributed algorithm for hypergraph maximal matching, which we believe will be of interest beyond this result. In any hypergraph of rank r - where each hyperedge has at most r vertices - with n nodes and maximum degree Δ, this algorithm computes a maximal matching in O(r 5 log 6+log r Δ·log n) rounds. This hypergraph matching algorithm and its extensions also lead to a number of other results. In particular, we obtain a polylogarithmic-time deterministic distributed maximal independent set (MIS) algorithm for graphs with bounded neighborhood independence, hence answering Open Problem 5 of Barenboim and Elkins book, a ((log Δ/ε) O(log 1/ε) )-round deterministic algorithm for (1+ε)-approximation of maximum matching, and a quasi-polylogarithmic-time deterministic distributed algorithm for orienting λ-arboricity graphs with out-degree at most ⌈(1+ε)λ⌉, for any constant ε>0, hence partially answering Open Problem 10 of Barenboim and Elkin's book.