21 citations · 75 across the 21 of their papers we have counts for
31 papers
Fully Scalable MPC Algorithms for Clustering in High Dimension
Artur Czumaj, Guichen Gao, Shaofeng H. -C. Jiang +2
We design new parallel algorithms for clustering in high-dimensional Euclidean spaces. These algorithms run in the Massively Parallel Computation (MPC) model, and are fully scalabl…
Optimal (degree+1)-Coloring in Congested Clique
Sam Coy, Artur Czumaj, Peter Davies +1
We consider the distributed complexity of the (degree+1)-list coloring problem, in which each node of degree is assigned a palette of colors, and the goal is to…
On Parallel -Center Clustering
Sam Coy, Artur Czumaj, Gopinath Mishra
We consider the classic -center problem {in the constant dimensional Euclidean space} under a parallel setting, on the low-local-space Massively Parallel Computation (MPC) model…
Parallel Derandomization for Coloring
Sam Coy, Artur Czumaj, Peter Davies +1
Graph coloring problems are among the most fundamental problems in parallel and distributed computing, and have been studied extensively in both settings. In this context, designin…
Routing Schemes for Hybrid Communication Networks
Sam Coy, Artur Czumaj, Christian Scheideler +2
We consider the problem of computing routing schemes in the model of distributed computing where nodes have access to two fundamentally different communication mo…
Streaming Facility Location in High Dimension via Geometric Hashing
Artur Czumaj, Arnold Filtser, Shaofeng H. -C. Jiang +3
In Euclidean Uniform Facility Location (UFL), the input is a set of clients in and the goal is to place facilities to serve them, so as to minimize the total cost of…
Near-Shortest Path Routing in Hybrid Communication Networks
Sam Coy, Artur Czumaj, Michael Feldmann +5
Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20…
On Truly Parallel Time in Population Protocols
Artur Czumaj, Andrzej Lingas
The {\em parallel time} of a population protocol is defined as the average number of required interactions that an agent in the protocol participates, i.e., the quotient between th…
Deterministic Massively Parallel Connectivity
Sam Coy, Artur Czumaj
We consider the problem of designing fundamental graph algorithms on the model of Massive Parallel Computation (MPC). The input to the problem is an undirected graph with v…
Component Stability in Low-Space Massively Parallel Computation
Artur Czumaj, Peter Davies, Merav Parter
We study the power and limitations of component-stable algorithms in the low-space model of Massively Parallel Computation (MPC). Recently Ghaffari, Kuhn and Uitto (FOCS 2019) intr…
Streaming Algorithms for Geometric Steiner Forest
Artur Czumaj, Shaofeng H. -C. Jiang, Robert Krauthgamer +1
We consider an important generalization of the Steiner tree problem, the \emph{Steiner forest problem}, in the Euclidean plane: the input is a multiset ,…
Simple, Deterministic, Constant-Round Coloring in the Congested Clique
Artur Czumaj, Peter Davies, Merav Parter
We settle the complexity of the -coloring and -list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems r…
Haystack Hunting Hints and Locker Room Communication
Artur Czumaj, George Kontogeorgiou, Mike Paterson
We want to efficiently find a specific object in a large unstructured set, which we model by a random -permutation, and we have to do it by revealing just a single element. Clea…
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
Artur Czumaj, Peter Davies, Merav Parter
The Massively Parallel Computation (MPC) model is an emerging model which distills core aspects of distributed and parallel computation. It has been developed as a tool to solve (t…
A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs)
Artur Czumaj, Christian Sohler
The problem of characterizing testable graph properties (properties that can be tested with a number of queries independent of the input size) is a fundamental problem in the area…
Testable Properties in General Graphs and Random Order Streaming
Artur Czumaj, Hendrik Fichtenberger, Pan Peng +1
We present a novel framework closely linking the areas of property testing and data streaming algorithms in the setting of general graphs. It has been recently shown (Monemizadeh e…
Online Facility Location with Deletions
Marek Cygan, Artur Czumaj, Marcin Mucha +1
In this paper we study three previously unstudied variants of the online Facility Location problem, considering an intrinsic scenario when the clients and facilities are not only a…
Detecting cliques in CONGEST networks
Artur Czumaj, Christian Konrad
The problem of detecting network structures plays a central role in distributed computing. One of the fundamental problems studied in this area is to determine whether for a given…
Randomized Communication Without Network Knowledge
Artur Czumaj, Peter Davies
Radio networks are a long-studied model for distributed system of devices which communicate wirelessly. When these devices are mobile or have limited capabilities, the system is of…
Deterministic Blind Radio Networks
Artur Czumaj, Peter Davies
Ad-hoc radio networks and multiple access channels are classical and well-studied models of distributed systems, with a large body of literature on deterministic algorithms for fun…
Round Compression for Parallel Matching Algorithms
Artur Czumaj, Jakub Łącki, Aleksander Mądry +3
For over a decade now we have been witnessing the success of {\em massive parallel computation} (MPC) frameworks, such as MapReduce, Hadoop, Dryad, or Spark. One of the reasons for…
Exploiting Spontaneous Transmissions for Broadcasting and Leader Election in Radio Networks
Artur Czumaj, Peter Davies
We study two fundamental communication primitives: broadcasting and leader election in the classical model of multi-hop radio networks with unknown topology and without collision d…
Distributed Methods for Computing Approximate Equilibria
Artur Czumaj, Argyrios Deligkas, Michail Fasoulakis +3
We present a new, distributed method to compute approximate Nash equilibria in bimatrix games. In contrast to previous approaches that analyze the two payoff matrices at the same t…
Deterministic Communication in Radio Networks
Artur Czumaj, Peter Davies
In this paper we improve the deterministic complexity of two fundamental communication primitives in the classical model of ad-hoc radio networks with unknown topology: broadcastin…