Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 61 Issue 1, January 2014

Linear-Time Approximation for Maximum Weight Matching
Ran Duan, Seth Pettie
Article No.: 1
DOI: 10.1145/2529989

The maximum cardinality and maximum weight matching problems can be solved in Õ(mn) time, a bound that has resisted improvement despite decades of research. (Here m and n are the...

Nonuniform ACC Circuit Lower Bounds
Ryan Williams
Article No.: 2
DOI: 10.1145/2559903

The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m > 1 is an arbitrary constant. We prove the following.

---NEXP, the class of languages accepted...

Constraint Satisfaction Problems Solvable by Local Consistency Methods
Libor Barto, Marcin Kozik
Article No.: 3
DOI: 10.1145/2556646

We prove that constraint satisfaction problems without the ability to count are solvable by the local consistency checking algorithm. This settles three (equivalent) conjectures: Feder--Vardi [SICOMP’98], Bulatov [LICS’04] and...

Sparser Johnson-Lindenstrauss Transforms
Daniel M. Kane, Jelani Nelson
Article No.: 4
DOI: 10.1145/2559902

We give two different and simple constructions for dimensionality reduction in 2 via linear mappings that are sparse: only an O(ϵ)-fraction of entries in each column of our embedding matrices are non-zero...

Approximating Markov Processes by Averaging
Philippe Chaput, Vincent Danos, Prakash Panangaden, Gordon Plotkin
Article No.: 5
DOI: 10.1145/2537948

Normally, one thinks of probabilistic transition systems as taking an initial probability distribution over the state space into a new probability distribution representing the system after a transition. We, however, take a dual view of Markov...

Foreword to Invited Articles Section
Victor Vianu
Article No.: 6
DOI: 10.1145/2559908

The Space Complexity of Long-Lived and One-Shot Timestamp Implementations
Maryam Helmi, Lisa Higham, Eduardo Pacheco, Philipp Woelfel
Article No.: 7
DOI: 10.1145/2559904

This article is concerned with the problem of implementing an unbounded timestamp object from multiwriter atomic registers, in an asynchronous distributed system of n processes with distinct identifiers where timestamps are taken from an...

Querying Regular Graph Patterns
Pablo Barceló, Leonid Libkin, Juan L. Reutter
Article No.: 8
DOI: 10.1145/2559905

Graph data appears in a variety of application domains, and many uses of it, such as querying, matching, and transforming data, naturally result in incompletely specified graph data, that is, graph patterns. While queries need to be posed against...