Search ACM DL

Search Issue

enter search term and/or author name

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