Arrow Research search

Author name cluster

Artur Czumaj

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

48 papers
2 author rows

Possible papers

48

MFCS Conference 2023 Conference Paper

Modern Parallel Algorithms (Invited Talk)

  • Artur Czumaj

Recent advances in the design of efficient parallel algorithms have been largely focusing on the nowadays classical model of parallel computing called Massive Parallel Computation (MPC), which follows the framework of MapReduce systems. In this talk we will survey recent advances in the design of algorithms for graph problems for the MPC model and will mention some interesting open questions in this area.

Details

STOC Conference 2022 Conference Paper

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 G with n vertices and m edges, and with D being the maximum diameter of any connected component in G . We consider the MPC with low local space , allowing each machine to store only Θ( n δ ) words for an arbitrary constant δ>0, and with linear global space (which is the number of machines times the local space available), that is, with optimal utilization. In a recent breakthrough, Andoni et al. (FOCS’18) and Behnezhad et al. (FOCS’19) designed parallel randomized algorithms that in O (log D + loglog n ) rounds on an MPC with low local space determine all connected components of a graph, improving on the classic bound of O (log n ) derived from earlier works on PRAM algorithms. In this paper, we show that asymptotically identical bounds can be also achieved for deterministic algorithms: we present a deterministic MPC low local space algorithm that in O (log D + loglog n ) rounds determines connected components of the input graph. Our result matches the complexity of state of the art randomized algorithms for this task. The techniques developed in our paper can be also applied to several related problems, giving new deterministic MPC algorithms for problems like finding a spanning forest, minimum spanning forest, etc. We complement our upper bounds by extending a recent lower bound for connectivity on an MPC conditioned on the 1-vs-2-cycles conjecture (which requires D ≥ log 1+Ω(1) n ), by showing a related conditional hardness of Ω(log D ) MPC rounds for the entire spectrum of D , covering a particularly interesting range when D ≤ O (log n ).

Details

FOCS Conference 2022 Conference Paper

Streaming Facility Location in High Dimension via Geometric Hashing

  • Artur Czumaj
  • Shaofeng H. -C. Jiang
  • Robert Krauthgamer
  • Pavel Veselý 0001
  • Mingwei Yang 0002

In Euclidean Uniform Facility Location, the input is a set of clients in $\mathrm{R}^{d}$ and the goal is to place facilities to serve them, so as to minimize the total cost of opening facilities plus connecting the clients. We study the classical setting of dynamic geometric streams, where the clients are presented as a sequence of insertions and deletions of points in the grid $\{1, ldots\, \Delta \}^{d}$, and we focus on the high-dimensional regime, where the algorithm’s space complexity must be polynomial (and certainly not exponential) in $d \cdot \log \Delta$. We present a new algorithmic framework, based on importance sampling from the stream, for $O(1)$-approximation of the optimal cost using only poly $(d\cdot\log\Delta)$ space. This framework is easy to implement in two passes, one for sampling points and the other for estimating their contribution. Over random-order streams, we can extend this to a one-pass algorithm by using the two halves of the stream separately. Our main result, for arbitrary-order streams, computes $O(d^{1. 5})$-approximation in one pass by using the new framework but combining the two passes differently. This improves upon previous algorithms that either need space exponential in d or only guarantee $O(d\cdot\log^{2}\Delta)$-approximation, and therefore our algorithms for high-dimensional streams are the first to avoid the $O(\log\Delta)$ factor in approximation that is inherent to the widely-used quadtree decomposition. Our improvement is achieved by employing a geometric hashing scheme that maps points in $\mathbb{R}^{d}$ into buckets of bounded diameter, with the key property that every point set of small-enough diameter is hashed into at most poly $(d)$ distinct buckets. Finally, we complement our results with a proof that every streaming 1. 085-approximation algorithm requires space exponential in poly $(d \cdot log \Delta)$, even for insertion-only streams.

Details

FOCS Conference 2019 Conference Paper

A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's 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 of property testing. While there has been some extensive prior research characterizing testable graph properties in the dense graphs model and we have good understanding of the bounded degree graphs model, no similar characterization has been known for general graphs, with no degree bounds. In this paper we take on this major challenge and consider the problem of characterizing all testable graph properties in general planar graphs. We consider the model in which a general planar graph can be accessed by the random neighbor oracle that allows access to any given vertex and access to a random neighbor of a given vertex. We show that, informally, a graph property P is testable with one-sided error for general planar graphs if and only if testing P can be reduced to testing for a finite family of finite forbidden subgraphs. While our presentation focuses on planar graphs, our approach extends easily to general minor-free graphs. Our analysis of the necessary condition relies on a recent construction of canonical testers in the random neighbor oracle model that is applied here to the one-sided error model for testing in planar graphs. The sufficient condition in the characterization reduces the problem to the task of testing H-freeness in planar graphs, and is the main and most challenging technical contribution of the paper: we show that for planar graphs (with arbitrary degrees), the property of being H-free is testable with one-sided error for every finite graph H, in the random neighbor oracle model.

Details

STOC Conference 2016 Conference Paper

Relating two property testing models for bounded degree directed graphs

  • Artur Czumaj
  • Pan Peng 0001
  • Christian Sohler

We study property testing algorithms in directed graphs (digraphs) with maximum indegree and maximum outdegree upper bounded by d . For directed graphs with bounded degree, there are two different models in property testing introduced by Bender and Ron (2002). In the bidirectional model , one can access both incoming and outgoing edges while in the unidirectional model one can only access outgoing edges. In our paper we provide a new relation between the two models: we prove that if a property can be tested with constant query complexity in the bidirectional model, then it can be tested with sublinear query complexity in the unidirectional model. A corollary of this result is that in the unidirectional model (the model allowing only queries to the outgoing neighbors), every property in hyperfinite digraphs is testable with sublinear query complexity.

Details

IJCAI Conference 2015 Conference Paper

Approximate Nash Equilibria with Near Optimal Social Welfare

  • Artur Czumaj
  • Michail Fasoulakis
  • Marcin Jurdzinski

It is known that Nash equilibria and approximate Nash equilibria not necessarily optimize social optima of bimatrix games. In this paper, we show that for every fixed ε > 0, every bimatrix game (with values in [0, 1]) has an ε-approximate Nash equilibrium with the total payoff of the players at least a constant factor, (1 − √ 1 − ε)2, of the optimum. Furthermore, our result can be made algorithmic in the following sense: for every fixed 0 ≤ ε∗ < ε, if we can find an ε∗ -approximate Nash equilibrium in polynomial time, then we can find in polynomial time an ε-approximate Nash equilibrium with the total payoff of the players at least a constant factor of the optimum. Our analysis is especially tight in the case when ε ≥ 1 2. In this case, we show that for any bimatrix game there is an ε-approximate Nash equilibrium with constant size support whose social welfare is at least 2 √ ε − ε ≥ 0. 914 times the optimal social welfare. Furthermore, we demonstrate that our bound for the social welfare is tight, that is, for every ε ≥ 1 2 there is a bimatrix game for which every ε-approximate Nash equilibrium has social welfare at most 2 √ ε − ε times the optimal social welfare.

PDF Details

STOC Conference 2011 Conference Paper

Almost tight bounds for reordering buffer management

  • Anna Adamaszek
  • Artur Czumaj
  • Matthias Englert
  • Harald Räcke

We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first non-trivial lower bounds for this problem by showing that deterministic online algorithms have a competitive ratio of at least Ω(√{log k/log log k}) and randomized online algorithms have a competitive ratio of at least Ω(log log k), where k denotes the size of the buffer. We complement this by presenting a deterministic online algorithm for the reordering buffer management problem that obtains a competitive ratio of O(√log k), almost matching the lower bound. This improves upon an algorithm by Avigdor-Elgrabli and Rabani (SODA 2010) that achieves a competitive ratio of O(log k/ log log k).

Details

FOCS Conference 2011 Conference Paper

Planar Graphs: Random Walks and Bipartiteness Testing

  • Artur Czumaj
  • Morteza Monemizadeh
  • Krzysztof Onak
  • Christian Sohler

We initiate the study of the testability of properties in arbitrary planar graphs. We prove that bipartiteness can be tested in constant time. The previous bound for this class of graphs was O(√n), and the constant-time testability was only known for planar graphs with bounded degree. Previously used transformations of unbounded-degree sparse graphs into bounded- degree sparse graphs cannot be used to reduce the problem to the testability of bounded-degree planar graphs. Our approach extends to arbitrary minor-free graphs. Our algorithm is based on random walks. The challenge here is to analyze random walks for a class of graphs that has good separators, i. e. , bad expansion. Standard techniques that use a fast convergence to a uniform distribution do not work in this case. Roughly speaking, our analysis technique self-reduces the problem of finding an odd-length cycle in a multigraph G induced by a collection of cycles to another multigraph G' induced by a set of shorter odd-length cycles, in such a way that when a random walks finds a cycle in G' with probability p >; 0, then it does so with probability λ(p) >; 0 in G. This reduction is applied until the cycles collapse to self-loops that can be easily detected.

Details

FOCS Conference 2007 Conference Paper

Testing Expansion in Bounded-Degree Graphs

  • Artur Czumaj
  • Christian Sohler

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an alpha-expander is a graph G = (V, E) in which even-subset U sube V of at most |V|/2 vertices has a neighborhood of size at least alphaldr|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time O tilde(radicn). We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every alpha-expander with probability at least 2/3 and rejects every graph that is epsiv-far from an alpha*-expander with probability at least 2/3, where alpha*=Theta(alpha 2 /(d 2 log (n/epsiv))) and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d 2 (radicn log (n/epsiv))/alpha 2 epsiv 3 ).

Details

FOCS Conference 2003 Conference Paper

Broadcasting Algorithms in Radio Networks with Unknown Topology

  • Artur Czumaj
  • Wojciech Rytter

In this paper we present new randomized and deterministic algorithms for the classical problem of broadcasting in radio networks with unknown topology. We consider directed n-node radio networks with specified eccentricity D (maximum distance from the source node to any other node). Our first main result closes the gap between the lower and upper bound: we describe an optimal randomized broadcasting algorithm whose running time complexity is O(D log(n/D) + log/sup 2/n), with high probability. In particular, we obtain a randomized algorithm that completes broadcasting in any n-node radio network in time O(n), with high probability. The main source of our improvement is a better "selecting sequence" used by the algorithm that brings some stronger property and improves the broadcasting time. Next, we demonstrate how to apply our approach to deterministic broadcasting, and describe a deterministic oblivious algorithm that completes broadcasting in almost optimal time O(n log/sup 2/D). Finally, we show how our randomized broadcasting algorithm can be used to improve the randomized complexity of the gossiping problem.

Details

FOCS Conference 2002 Conference Paper

Abstract Combinatorial Programs and Efficient Property Testers

  • Artur Czumaj
  • Christian Sohler

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms with one-sided error. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of classical combinatorial problems. Among others, we present efficient property testing algorithms for geometric clustering problems, the reversal distance problem, and graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way and the obtained complexity bounds either match or improve the previously known bounds. We believe that our framework will help to better understand the structure of efficiently testable properties.

Details

FOCS Conference 1997 Conference Paper

Randomized Allocation Processes

  • Artur Czumaj
  • Volker Stemann

We investigate various randomized processes allocating balls into bins that arise in applications in dynamic resource allocation and on-line load balancing. We consider the scenario when m balls arriving sequentially are to be allocated into n bins on-line and without using a global controller. Traditionally, the main aim of allocation processes is to place the balls into bins to minimize the maximum load in bins. However in many applications it is equally important to minimize the number of trails performed by the balls (the allocation time). We study adaptive allocation schemes that achieve optimal tradeoffs between the maximum load, the maximum allocation time, and the average allocation time. We investigate allocation processes that may reallocate the balls. We provide a tight analysis of the maximum load of processes that during placing a new ball may reassign the balls in up to d randomly chosen bins. We study infinite processes, in which in each step a random ball is removed and a new ball is placed according to some scheduling rule. We present a novel approach that establishes a tight estimation of the time needed for the infinite process to be in the state near to its equilibrium. Finally, we provide a tight analysis of the maximum load of the off-line process in which each ball may be placed into one of d randomly chosen bins. We apply this result to competitive analysis of on-line load balancing processes.

Details

MFCS Conference 1996 Conference Paper

Parallel Alternating-Direction Access Machine

  • Bogdan S. Chlebus
  • Artur Czumaj
  • Leszek Gasieniec
  • Miroslaw Kowaluk
  • Wojciech Plandowski

Abstract This paper presents a theoretical study of a model of parallel computations called Parallel Alternating-Direction Access Machine ( Padam ). Padam is an abstraction of the multiprocessor computers Adena /adenart and a prototype architecture usc/omp. The main feature of Padam is the organization of access to the global memory: (1) the memory modules are arranged as a 2-dimensional array, (2) each processor is assigned to a row and a column, (3) the processors switch synchronously between row and column access modes, and can access any of the assigned modules in each mode without conflicts. Since the padam processors have such a restricted access to the partially shared memory, developing tools to enhance flexibility of access to the memory is important. The paper concentrates on these issues.

Details