Arrow Research search

Author name cluster

David Richerby

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers
2 author rows

Possible papers

9

STOC Conference 2010 Conference Paper

On the complexity of #CSP

  • Martin E. Dyer
  • David Richerby

Bulatov (2008) has given a dichotomy for the counting constraint satisfaction problem, #CSP. A problem from #CSP is characterized by a constraint language γ, which is a fixed, finite set of relations over a finite domain. An instance of the problem uses these relations to constrain the values taken by a finite set of variables. Bulatov showed that, for any fixed γ, the problem of counting the satisfying assignments of instances of any problem from #CSP is either in polynomial time (FP) or #P-complete, according on the structure of the constraint language γ. His proof draws heavily on techniques from universal algebra and cannot be understood without a secure grasp of that field. We give an elementary proof of Bulatov's dichotomy, based on succinct representations, which we call frames, of a class of highly structured relations, which we call strongly rectangular. We show that these are precisely the relations that are invariant under a Mal'tsev polymorphism. En route, we give a simplification of a decision algorithm for strongly rectangular constraint languages due to Bulatov and Dalmau (2006). Out proof uses no universal algebra, except for the straightforward concept of the Mal'tsev polymorphism and is accessible to readers with little background in #CSP.

Details

CSL Conference 2007 Conference Paper

The Power of Counting Logics on Restricted Classes of Finite Structures

  • Anuj Dawar
  • David Richerby

Abstract Although Cai, Fürer and Immerman have shown that fixed-point logic with counting (IFP+C) does not express all polynomial-time properties of finite structures, there have been a number of results demonstrating that the logic does capture P on specific classes of structures. Grohe and Mariño showed that IFP+C captures P on classes of structures of bounded treewidth, and Grohe showed that IFP+C captures P on planar graphs. We show that the first of these results is optimal in two senses. We show that on the class of graphs defined by a non-constant bound on the tree-width of the graph, IFP+C fails to capture P. We also show that on the class of graphs whose local tree-width is bounded by a non-constant function, IFP+C fails to capture P. Both these results are obtained by an analysis of the Cai–Fürer–Immerman (CFI) construction in terms of the treewidth of graphs, and cops and robber games; we present some other implications of this analysis. We then demonstrate the limits of this method by showing that the CFI construction cannot be used to show that IFP+C fails to capture P on proper minor-closed classes.

Details

CSL Conference 2004 Conference Paper

Logical Characterizations of PSPACE

  • David Richerby

Abstract We present two, quite different, logical characterizations of the computational complexity class PSPACE on unordered, finite relational structures. The first of these, the closure of second-order logic under the formation of partial fixed points is well-known in the folklore but does not seem to be in the literature. The second, the closure of first-order logic under taking partial fixed points and under an operator for nondeterministic choice, is novel. We also present syntactic normal forms for the two logics and compare the second with other choice-based fixed-point logics found in the literature.

Details

CSL Conference 2003 Conference Paper

A Fixed-Point Logic with Symmetric Choice

  • Anuj Dawar
  • David Richerby

Abstract Gire and Hoang introduce a fixed-point logic with a ‘symmetric’ choice operator that makes a nondeterministic choice from a definable set of tuples at each stage in the inductive construction of a relation, as long as the set of tuples is an automorphism class of the structure. We present a clean definition of the syntax and semantics of this logic and investigate its expressive power. We extend the logic of Gire and Hoang with parameterized and nested fixed points and first-order combinations of fixed points. We show that the ability to supply parameters to fixed points strictly increases the power of the logic. Our logic can express the graph isomorphism problem and we show that, on almost all structures, it captures P GI, the class of problems decidable in polynomial time by a deterministic Turing machine with an oracle for graph isomorphism.

Details