Search ACM DL

Search Issue

enter search term and/or author name

Section:

**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: *

*
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: *

*
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: *

*
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: *

*
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...
*