Hans-Joerg Burtschick, Heribert Vollmer

We show that examinations of the expressive power of logical formulae

enriched by Lindstroem quantifiers over ordered finite structures

have a well-studied complexity-theoretic counterpart: the leaf

language approach to define complexity classes. Model classes of

formulae with Lindstroem quantifiers are nothing else than leaf

language definable sets. Along the ...
more >>>

C. Lautemann, Pierre McKenzie, T. Schwentick, H. Vollmer

Building upon the known generalized-quantifier-based first-order

characterization of LOGCFL, we lay the groundwork for a deeper

investigation. Specifically, we examine subclasses of LOGCFL arising

from varying the arity and nesting of groupoidal quantifiers. Our

work extends the elaborate theory relating monoidal quantifiers to

NC^1 and its subclasses. In the ...
more >>>

Till Tantau

The reachability problem for graphs cannot be described, in the

sense of descriptive complexity theory, using a single first-order

formula. This is true both for directed and undirected graphs, both

in the finite and infinite. However, if we restrict ourselves to

graphs in which a certain graph parameter is fixed ...
more >>>

Philipp Weis, Neil Immerman

It is well-known that every first-order property on words is expressible

using at most three variables. The subclass of properties expressible with

only two variables is also quite interesting and well-studied. We prove

precise structure theorems that characterize the exact expressive power of

first-order logic with two variables on words. ...
more >>>

Martin Grohe

Algorithmic meta theorems are algorithmic results that apply to whole families of combinatorial problems, instead of just specific problems. These families are usually defined in terms of logic and graph theory. An archetypal algorithmic meta theorem is Courcelle's Theorem, which states that all graph properties definable in monadic second-order logic ... more >>>

Stephan Kreutzer, Anuj Dawar

We show that if $\mathcal C$ is a class of graphs which is

"nowhere dense" then first-order model-checking is

fixed-parameter tractable on $\mathcal C$. As all graph classes which exclude a fixed minor, or are of bounded local tree-width or locally exclude a minor are nowhere dense, this generalises algorithmic ...
more >>>

Albert Atserias, Elitza Maneva

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the notion of fractional isomorphism. We show ... more >>>

Prabhu Manyem, Julien Ugon

We survey research that studies the connection between the computational complexity

of optimization problems on the one hand, and the duality gap between the primal and

dual optimization problems on the other. To our knowledge, this is the first survey that

connects the two very important areas. We further look ...
more >>>

Albert Atserias, Anuj Dawar

Kolaitis and Kopparty have shown that for any first-order formula with

parity quantifiers over the language of graphs there is a family of

multi-variate polynomials of constant-degree that agree with the

formula on all but a $2^{-\Omega(n)}$-fraction of the graphs with $n$

vertices. The proof yields a bound on the ...
more >>>