enter search term and/or author name
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
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
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
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
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
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...
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...
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...