Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 60 Issue 5, October 2013

Editorial: JACM redux
Victor Vianu
Article No.: 30
DOI: 10.1145/2528384.2528385

Fast matrix rank algorithms and applications
Ho Yee Cheung, Tsz Chiu Kwok, Lap Chi Lau
Article No.: 31
DOI: 10.1145/2528404

We consider the problem of computing the rank of an m × n matrix A over a field. We present a randomized algorithm to find a set of r = rank(A) linearly independent columns in...

The expressibility of functions on the boolean domain, with applications to counting CSPs
Andrei A. Bulatov, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Colin Mcquillan
Article No.: 32
DOI: 10.1145/2528401

An important tool in the study of the complexity of Constraint Satisfaction Problems (CSPs) is the notion of a relational clone, which is the set of all relations expressible using primitive positive formulas over a particular set of base...

From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits
Nitin Saxena, C. Seshadhri
Article No.: 33
DOI: 10.1145/2528403

We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities that improves the known deterministic...

The complexity of the counting constraint satisfaction problem
Andrei A. Bulatov
Article No.: 34
DOI: 10.1145/2528400

The Counting Constraint Satisfaction Problem (#CSP(H)) over a finite relational structure H can be expressed as follows: given a relational structure G over the same vocabulary, determine the number of homomorphisms from G to H. In this...

Towards a complexity theory for local distributed computing
Pierre Fraigniaud, Amos Korman, David Peleg
Article No.: 35
DOI: 10.1145/2499228

A central theme in distributed network algorithms concerns understanding and coping with the issue of locality. Yet despite considerable progress, research efforts in this direction have not yet resulted in a solid basis in the form of a...

Testing first-order properties for subclasses of sparse graphs
Zdeněk Dvořák, Daniel Král, Robin Thomas
Article No.: 36
DOI: 10.1145/2499483

We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nešetřil and Ossona de Mendez. This generalizes several results from the...

Random graphs and the parity quantifier
Phokion G. Kolaitis, Swastik Kopparty
Article No.: 37
DOI: 10.1145/2528402

The classical zero-one law for first-order logic on random graphs says that for every first-order property ϕ in the theory of graphs and every p ∈ (0,1), the probability that the random graph G(n, p) satisfies...

Invited article foreword
Victor Vianu
Article No.: 38
DOI: 10.1145/2528384.2528386

Lower bounds for local approximation
Mika Göös, Juho Hirvonen, Jukka Suomela
Article No.: 39
DOI: 10.1145/2528405

In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique O(log n)-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed...