b'Fabian Kuhn'

research

∙ 08/08/2023

On the Node-Averaged Complexity of Locally Checkable Problems on Trees

Over the past decade, a long line of research has investigated the distr...

0 Alkida Balliu, et al. ∙

research

∙ 07/18/2023

No distributed quantum advantage for approximate graph coloring

We give an almost complete characterization of the hardness of c-colorin...

0 Xavier Coiteux-Roy, et al. ∙

research

∙ 06/01/2023

Time and Space Optimal Massively Parallel Algorithm for the 2-Ruling Set Problem

In this work, we present a constant-round algorithm for the 2-ruling set...

0 Mélanie Cambus, et al. ∙

research

∙ 04/19/2023

Coloring Fast with Broadcasts

We present an O(log^3log n)-round distributed algorithm for the (Δ+1)-co...

0 Maxime Flin, et al. ∙

research

∙ 04/19/2023

List Defective Colorings: Distributed Algorithms and Applications

The distributed coloring problem is at the core of the area of distribut...

0 Marc Fuchs, et al. ∙

research

∙ 01/16/2023

A Distributed Palette Sparsification Theorem

Is fully decentralized graph streaming possible? We consider this questi...

0 Maxime Flin, et al. ∙

research

∙ 11/03/2022

Distributed Maximal Matching and Maximal Independent Set on Hypergraphs

We investigate the distributed complexity of maximal matching and maxima...

0 Alkida Balliu, et al. ∙

research

∙ 09/23/2022

Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond

We develop a general deterministic distributed method for locally roundi...

0 Salwa Faour, et al. ∙

research

∙ 08/17/2022

Node and Edge Averaged Complexities of Local Graph Problems

The node-averaged complexity of a distributed algorithm running on a gra...

0 Alkida Balliu, et al. ∙

research

∙ 07/24/2022

Contention Resolution for Coded Radio Networks

Randomized backoff protocols, such as exponential backoff, are a powerfu...

0 Michael A. Bender, et al. ∙

research

∙ 06/02/2022

Distributed Edge Coloring in Time Polylogarithmic in Δ

We provide new deterministic algorithms for the edge coloring problem, w...

0 Alkida Balliu, et al. ∙

research

∙ 02/16/2022

Near-Shortest Path Routing in Hybrid Communication Networks

Hybrid networks, i.e., networks that leverage different means of communi...

0 Sam Coy, et al. ∙

research

∙ 02/14/2022

Routing Schemes and Distance Oracles in the Hybrid Model

The 𝖧𝖸𝖡𝖱𝖨𝖣 model was introduced as a means for theoretical study of dist...

0 Fabian Kuhn, et al. ∙

research

∙ 12/08/2021

Improved Distributed Fractional Coloring Algorithms

We prove new bounds on the distributed fractional coloring problem in th...

0 Alkida Balliu, et al. ∙

research

∙ 12/01/2021

Near-Optimal Distributed Degree+1 Coloring

We present a new approach to randomized distributed graph coloring that ...

0 Magnus M. Halldorsson, et al. ∙

research

∙ 11/20/2021

Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings

We provide CONGEST model algorithms for approximating minimum weighted v...

0 Salwa Faour, et al. ∙

research

∙ 10/01/2021

Distributed Δ-Coloring Plays Hide-and-Seek

We prove several new tight distributed lower bounds for classic symmetry...

0 Alkida Balliu, et al. ∙

research

∙ 06/04/2021

Improved Distributed Lower Bounds for MIS and Bounded (Out-)Degree Dominating Sets in Trees

Recently, Balliu, Brandt, and Olivetti [FOCS '20] showed the first ω(log...

0 Alkida Balliu, et al. ∙

research

∙ 12/28/2020

Efficient Randomized Distributed Coloring in CONGEST

Distributed vertex coloring is one of the classic problems and probably ...

0 Magnus M. Halldorsson, et al. ∙

research

∙ 11/19/2020

Approximate Bipartite Vertex Cover in the CONGEST Model

We give efficient distributed algorithms for the minimum vertex cover pr...

0 Salwa Faour, et al. ∙

research

∙ 11/09/2020

Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition

We present a simple deterministic distributed algorithm that computes a ...

0 Mohsen Ghaffari, et al. ∙

research

∙ 08/10/2020

Coloring Fast Without Learning Your Neighbors' Colors

We give an improved randomized CONGEST algorithm for distance-2 coloring...

0 Magnus M. Halldorsson, et al. ∙

research

∙ 06/15/2020

Computing Shortest Paths and Diameter in the Hybrid Network Model

The 𝖧𝖸𝖡𝖱𝖨𝖣 model, introduced in [Augustine et al., SODA '20], provides a...

0 Fabian Kuhn, et al. ∙

research

∙ 05/13/2020

Distance-2 Coloring in the CONGEST Model

We give efficient randomized and deterministic distributed algorithms fo...

0 Magnus M. Halldorsson, et al. ∙

research

∙ 02/25/2020

Distributed Edge Coloring in Time Quasi-Polylogarithmic in Delta

The problem of coloring the edges of an n-node graph of maximum degree Δ...

0 Alkida Balliu, et al. ∙

research

∙ 02/18/2020

Distributed Maximum Matching Verification in CONGEST

We study the maximum cardinality matching problem in a standard distribu...

0 Mohamad Ahmadi, et al. ∙

research

∙ 12/05/2019

Efficient Deterministic Distributed Coloring with Small Bandwidth

We show that the (degree+1)-list coloring problem can be solved determin...

0 Philipp Bamberger, et al. ∙

research

∙ 09/04/2019

Shortest Paths in a Hybrid Network Model

We introduce a communication model for hybrid networks, where nodes have...

0 John Augustine, et al. ∙

research

∙ 07/08/2019

Faster Deterministic Distributed Coloring Through Recursive List Coloring

We provide novel deterministic distributed vertex coloring algorithms. A...

0 Fabian Kuhn, et al. ∙

research

∙ 06/02/2019

On the Use of Randomness in Local Distributed Graph Algorithms

We attempt to better understand randomization in local distributed graph...

0 Mohsen Ghaffari, et al. ∙

research

∙ 05/28/2019

On the Complexity of Distributed Splitting Problems

One of the fundamental open problems in the area of distributed graph al...

0 Philipp Bamberger, et al. ∙

research

∙ 05/26/2019

Deterministic Distributed Dominating Set Approximation in the CONGEST Model

We develop deterministic approximation algorithms for the minimum domina...

0 Janosch Deurer, et al. ∙

research

∙ 02/24/2019

Latency, Capacity, and Distributed MST

Consider the problem of building a minimum-weight spanning tree for a gi...

0 John Augustine, et al. ∙

research

∙ 02/20/2019

Competitive Concurrent Distributed Scheduling

We introduce a new scheduling problem in distributed computing that we c...

0 Abdolhamid Ghodselahi, et al. ∙

research

∙ 09/18/2018

Optimal strategies for patrolling fences

A classical multi-agent fence patrolling problem asks: What is the maxim...

0 Bernhard Haeupler, et al. ∙

research

∙ 06/26/2018

The Communication Cost of Information Spreading in Dynamic Networks

This paper investigates the message complexity of distributed informatio...

0 Mohamad Ahmadi, et al. ∙

research

∙ 05/18/2018

Distributed Computation in the Node-Congested Clique

The Congested Clique model of distributed computing, which was introduce...

0 John Augustine, et al. ∙

research

∙ 05/18/2018

Deterministic Distributed Ruling Sets of Line Graphs

An (α,β)-ruling set of a graph G=(V,E) is a set R⊆ V such that for any n...

0 Fabian Kuhn, et al. ∙

research

∙ 05/09/2018

Efficient Distributed Computation of MIS and Generalized MIS in Linear Hypergraphs

Given a graph, a maximal independent set (MIS) is a maximal subset of pa...

0 Fabian Kuhn, et al. ∙

research

∙ 03/08/2018

Improved Distributed Δ-Coloring

We present a randomized distributed algorithm that computes a Δ-coloring...

0 Mohsen Ghaffari, et al. ∙

research

∙ 02/27/2018

Local Distributed Algorithms in Highly Dynamic Networks

The present paper studies local distributed graph problems in highly dyn...

0 Philipp Bamberger, et al. ∙

research

∙ 11/15/2017

Deterministic Distributed Edge-Coloring with Fewer Colors

We present a deterministic distributed algorithm, in the LOCAL model, th...

0 Mohsen Ghaffari, et al. ∙

research

∙ 11/06/2017

On Derandomizing Local Distributed Algorithms

The gap between the known randomized and deterministic local distributed...

0 Mohsen Ghaffari, et al. ∙

Fabian Kuhn

Featured Co-authors