Source author record

Artur Czumaj

Artur Czumaj appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Computer Science and Game Theory Discrete Mathematics

Catalog footprint

What is connected

6works

4topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Near-Shortest Path Routing in Hybrid Communication Networks

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] introduced the $\mathsf{HYBRID}$ model, which is based on the concept of synchronous message passing and uses two fundamentally different principles of communication: a local mode, which allows every node to exchange one message per round with each neighbor in a local communication graph; and a global mode where any pair of nodes can exchange messages, but only few such exchanges can take place per round. A sizable portion of the previous research for the $\mathsf{HYBRID}$ model revolves around basic communication primitives and computing distances or shortest paths in networks. In this paper, we extend this study to a related fundamental problem of computing compact routing schemes for near-shortest paths in the local communication graph. We demonstrate that, for the case where the local communication graph is a unit-disc graph with $n$ nodes that is realized in the plane and has no radio holes, we can deterministically compute a routing scheme that has constant stretch and uses labels and local routing tables of size $O(\log n)$ bits in only $O(\log n)$ rounds.

preprint2020arXiv

Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space

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 (typically graph) problems in systems where the input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in $n$, the number of nodes in the input graph) memory, with randomized algorithms presented for fundamental graph problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding \emph{deterministic} algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all the edges incident to a single node. This poses a considerable obstacle compared to the classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier we introduce a new \emph{graph sparsification technique} that \emph{deterministically} computes a low-degree subgraph with additional desired properties. Using this framework to derandomize the well-known randomized algorithm of Luby [SICOMP'86], we obtain $O(\log Δ+\log\log n)$-round \emph{deterministic} MPC algorithms for solving the fundamental problems of \emph{Maximal Matching} and \emph{Maximal Independent Set} with $O(n^ε)$ space on each machine for any constant $ε> 0$. Based on the recent work of Ghaffari et al. [FOCS'18], this additive $O(\log\log n)$ factor is \emph{conditionally} essential. These algorithms can also be shown to run in $O(\log Δ)$ rounds in the closely related model of \congc, improving upon the state-of-the-art bound of $O(\log^2 Δ)$ rounds by Censor-Hillel et al. [DISC'17].

preprint2020arXiv

Simple, Deterministic, Constant-Round Coloring in the Congested Clique

We settle the complexity of the $(Δ+1)$-coloring and $(Δ+1)$-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round $(Δ+1)$-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art $O(\log Δ)$-round deterministic $(Δ+1)$-coloring bound of Parter (ICALP'18). A remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang et al. (STOC'18), our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after $O(1)$ recursion steps, the remaining uncolored subgraph within each bin has linear size, and thus can be solved locally by collecting it to a single node. This algorithm can also be implemented in the Massively Parallel Computation (MPC) model provided that each machine has linear (in $n$, the number of nodes in the input graph) space. We also show an extension of our algorithm to the MPC regime in which machines have sublinear space: we present the first deterministic $(Δ+1)$-list coloring algorithm designed for sublinear-space MPC, which runs in $O(\log Δ+ \log\log n)$ rounds.

preprint2015arXiv

Testing Cluster Structure of Graphs

We study the problem of recognizing the cluster structure of a graph in the framework of property testing in the bounded degree model. Given a parameter $\varepsilon$, a $d$-bounded degree graph is defined to be $(k, ϕ)$-clusterable, if it can be partitioned into no more than $k$ parts, such that the (inner) conductance of the induced subgraph on each part is at least $ϕ$ and the (outer) conductance of each part is at most $c_{d,k}\varepsilon^4ϕ^2$, where $c_{d,k}$ depends only on $d,k$. Our main result is a sublinear algorithm with the running time $\widetilde{O}(\sqrt{n}\cdot\mathrm{poly}(ϕ,k,1/\varepsilon))$ that takes as input a graph with maximum degree bounded by $d$, parameters $k$, $ϕ$, $\varepsilon$, and with probability at least $\frac23$, accepts the graph if it is $(k,ϕ)$-clusterable and rejects the graph if it is $\varepsilon$-far from $(k, ϕ^*)$-clusterable for $ϕ^* = c'_{d,k}\frac{ϕ^2 \varepsilon^4}{\log n}$, where $c'_{d,k}$ depends only on $d,k$. By the lower bound of $Ω(\sqrt{n})$ on the number of queries needed for testing graph expansion, which corresponds to $k=1$ in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors.

preprint2014arXiv

Approximate well-supported Nash equilibria in symmetric bimatrix games

The $\varepsilon$-well-supported Nash equilibrium is a strong notion of approximation of a Nash equilibrium, where no player has an incentive greater than $\varepsilon$ to deviate from any of the pure strategies that she uses in her mixed strategy. The smallest constant $\varepsilon$ currently known for which there is a polynomial-time algorithm that computes an $\varepsilon$-well-supported Nash equilibrium in bimatrix games is slightly below $2/3$. In this paper we study this problem for symmetric bimatrix games and we provide a polynomial-time algorithm that gives a $(1/2+δ)$-well-supported Nash equilibrium, for an arbitrarily small positive constant $δ$.

preprint2012arXiv

Finding Cycles and Trees in Sublinear Time

We present sublinear-time (randomized) algorithms for finding simple cycles of length at least $k\geq 3$ and tree-minors in bounded-degree graphs. The complexity of these algorithms is related to the distance of the graph from being $C_k$-minor-free (resp., free from having the corresponding tree-minor). In particular, if the graph is far (i.e., $Ω(1)$-far) {from} being cycle-free, i.e. if one has to delete a constant fraction of edges to make it cycle-free, then the algorithm finds a cycle of polylogarithmic length in time $\tildeO(\sqrt{N})$, where $N$ denotes the number of vertices. This time complexity is optimal up to polylogarithmic factors. The foregoing results are the outcome of our study of the complexity of {\em one-sided error} property testing algorithms in the bounded-degree graphs model. For example, we show that cycle-freeness of $N$-vertex graphs can be tested with one-sided error within time complexity $\tildeO(\poly(1/\e)\cdot\sqrt{N})$. This matches the known $Ω(\sqrt{N})$ query lower bound, and contrasts with the fact that any minor-free property admits a {\em two-sided error} tester of query complexity that only depends on the proximity parameter $\e$. For any constant $k\geq3$, we extend this result to testing whether the input graph has a simple cycle of length at least $k$. On the other hand, for any fixed tree $T$, we show that $T$-minor-freeness has a one-sided error tester of query complexity that only depends on the proximity parameter $\e$. Our algorithm for finding cycles in bounded-degree graphs extends to general graphs, where distances are measured with respect to the actual number of edges. Such an extension is not possible with respect to finding tree-minors in $o(\sqrt{N})$ complexity.