Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 64 Issue 3, June 2017

Section: Distributed Computing

Plane Formation by Synchronous Mobile Robots in the Three-Dimensional Euclidean Space
Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, Masafumi Yamashita
Article No.: 16
DOI: 10.1145/3060272

Creating a swarm of mobile computing entities, frequently called robots, agents, or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, we investigate the plane formation...

Section: Distributed Computing

Deciding First-Order Properties of Nowhere Dense Graphs
Martin Grohe, Stephan Kreutzer, Sebastian Siebertz
Article No.: 17
DOI: 10.1145/3051095

Nowhere dense graph classes, introduced by Nešetřil and Ossona de Mendez [2010, 2011], form a large variety of classes of “sparse graphs” including the class of planar graphs, actually all classes with excluded minors,...

Section: Distributed Computing

Tight Lower Bounds on Graph Embedding Problems
Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała
Article No.: 18
DOI: 10.1145/3051094

We prove that unless the Exponential Time Hypothesis (ETH) fails, deciding if there is a homomorphism from graph G to graph H cannot be done in time...

Section: Distributed Computing

Complexity of Counting CSP with Complex Weights
Jin-Yi Cai, Xi Chen
Article No.: 19
DOI: 10.1145/2822891

We give a complexity dichotomy theorem for the counting constraint satisfaction problem (#CSP in short) with algebraic complex weights. To this end, we give three conditions for its tractability. Let F be any finite set of algebraic...

Section: Distributed Computing

The Complexity of Non-Monotone Markets
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
Article No.: 20
DOI: 10.1145/3064810

We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove that it is PPAD-hard to compute an approximate Arrow-Debreu market equilibrium in markets with linear and...

Section: Distributed Computing

On Learning and Testing Dynamic Environments
Oded Goldreich, Dana Ron
Article No.: 21
DOI: 10.1145/3088509

We initiate a study of learning and testing dynamic environments, focusing on environments that evolve according to a fixed local rule. The (proper) learning task consists of obtaining the initial configuration of the environment, whereas for...

Section: Distributed Computing

Invited Article Foreword
Eva Tardos
Article No.: 22
DOI: 10.1145/3090999

Section: Distributed Computing

A Distributed (2 + ε)-Approximation for Vertex Cover in O(log Δ / ε log log Δ) Rounds
Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman
Article No.: 23
DOI: 10.1145/3060294

We present a simple deterministic distributed (2 + ε)-approximation algorithm for minimum-weight vertex cover, which completes in O(log Δ/εlog log Δ) rounds, where Δ is the maximum degree in the graph, for any...