Guest Post by Thomas Zeume on
Lower Bounds for Dynamic Descriptive Complexity
(A result that uses Ramsey Theory!)
In a previous blog post Bill mentioned his hobby to collect theorems that
apply Ramsey theory. I will present one such application that arises in
dynamic descriptive complexity theory. The first half of the post introduces
the setting, the second part sketches a lower bound proof that uses Ramsey theory.
Dynamic descriptive complexity theory studies which queries can be maintained by
first-order formulas with the help of auxiliary relations, when the input structure
is subject to simple modifications such as tuple insertions and tuple deletions.
As an example consider a directed graph into which edges are inserted. When an edge
(u, v) is inserted, then the new transitive closure T' can be defined from the old
transitive closure T by a first-order formula that uses u and v as parameters:
T'(x,y) = T(x,y) ∨ (T(x, u) ∧ T(v, y))
Thus the reachability query can be maintained under insertions in this fashion
(even though it cannot be expressed in first-order logic directly).
The above update formula is an example of a dynamic descriptive complexity program.
In general, dynamic programs may use several auxiliary relations that are helpful
to maintain the query under consideration. Then each auxiliary relation has one
update formula for edge insertions and one formula for edge deletions.
The example above uses a single auxiliary relation T (which is also the designated
query result) and only updates T under insertions.
This principle setting has been independently formalized in very similar ways by
Dong, Su and Topor [1, 2] and by Patnaik and Immerman [3]. For both groups one of
the main motivations was that first-order logic is the core of SQL and therefore
queries maintainable in this setting can also be maintained using SQL. Furthermore
the correspondance of first-order logic with built-in arithmetic to uniform
AC0-circuits (constant-depth circuits of polynomial size with unbounded fan-in)
yields that queries maintainable in this way can be evaluated dynamically in a
highly parallel fashion.
One of the main questions studied in Dynamic Complexity has been whether
Reachability on directed graphs can be maintained in DynFO
(under insertions and deletions of edges). Here DynFO is the class of
properties that can be maintained by first-order update formulas.
The conjecture by Patnaik and Immerman that this is possible has been recently
confirmed by Datta, Kulkarni, Mukherjee, Schwentick and the author of this post,
but has not been published yet [4].
In this blog post, I would like to talk about dynamic complexity LOWER rather
than upper bounds. Research on dynamic complexity lower bounds has not been
very successful so far. Even though there are routine methods to prove that a
property can not be expressed in first-order logic (or, for that matter, not in AC0),
the dynamic setting adds a considerable level of complication. So far, there is
no lower bound showing that a particular property can not be maintained in
DynFO (besides trivial bounds for properties beyond polynomial time).
For this reason, all (meaningful) lower bounds proved so far in this setting
have been proved for restricted dynamic programs. One such restriction is to
disallow the use of quantifiers in update formulas. The example above illustrates
that useful properties can be maintained even without quantifiers
(though in this example under insertions only). Therefore proving lower bounds
for this small syntactic fragment can be of interest.
Several lower bounds for quantifier-free dynamic programs have been proved by using
basic combinatorial tools. For example, counting arguments yield a lower bound for
alternating reachability and non-regular languages [5], and Ramsey-like theorems
as well as Higman's lemma can be used to prove that the reachability query
(under edge insertions and deletions) cannot be maintained by
quantifier-free dynamic programs with binary auxiliary relations [6].
Here, I will present how bounds for Ramsey numbers can be used to obtain lower bounds.
Surprisingly, the proof of the lower bound in the following result relies on both
upper and lower bounds for Ramsey numbers. Therefore the result might be a good candidate
for Bill's collection of theorems that use Ramsey-like results.
THEOREM (from [7])
When only edge insertions are allowed, then (k+2)-clique can be maintained by a
quantifier-free dynamic program with (k+1)-ary auxiliary relations, but it cannot be
maintained by such a program with k-ary auxiliary relations.
SKETCH OF PROOF
I present a (very) rough proof sketch of the lower bound in the theorem.
The proof sketch aims at giving a flavour of how the upper and lower bounds
on the size of Ramsey numbers are used to prove the above lower bound.
Instead of using bounds on Ramsey numbers, it will be more convenient to use
the following equivalent bounds on the size of Ramsey cliques. For every c and large enough n:
1) Every $c$-colored complete $k$-hypergraph of size n contains a large Ramsey clique.
2) There is a 2-coloring of the complete $(k+1)$-hypergraph of size n that does \emph{not} contain a large Ramsey clique.
In the following it is not necessary to know what "large" exactly means
(though it roughly means of size log^{k-1} n in both statements).
Those bounds are due to Rado, Hajnal and Erdős.
Towards a contradiction we assume that there is a quantifier-free program P with
k-ary auxiliary relations that maintains whether a graph contains a (k+2)-clique.
The first step is to construct a graph G = (V UNION W, E) such that in all large subsets
C of V one can find independent sets A and B of size k+1 such that adding all edges
between nodes of A yields a graph containing a (k+2)-clique while adding all edges
between nodes of B yields a graph without a (k+2)-clique. Such a graph G can be constructed
using (2). (Choose a large set V and let W := V^{k+1}. Color the set W according to
(2) with colors red and blue. Connect all blue elements w = (v_1, ..., v_{k+1}) in W
with the elements v_1, \ldots, v_{k+1} in V.)
Now, if the program P currently stores G, then within the current auxiliary relations
stored by P one can find a large subset C of V where all k-tuples are colored equally
by the auxiliary relations. Such a set C can be found using (1). (More precisely:
by a slight extension of (1) to structures.)
By the construction of G there are subsets A and B of the set C with the property stated
above. As A and B are subsets of C, they are isomorphic with respect to the auxiliary
relations and the edge relation. A property of quantifier-free programs is that for such
isomorphic sets, the application of corresponding modification sequences yields the same
answer of the program, where "corresponding" means that they adhere to the isomorphism.
Thus the dynamic program P will give the same answer when adding all edges of A, and whenadding all edges of B (in an order that preserves the isomorphism). This is a contradiction
as the first sequence of modifications yields a graph with a (k+2)-clique while the second
yields a graph without a (k+2)-clique. Hence such a program P cannot exist. This proves
the lower bound from the above theorem.
I thank Thomas Schwentick and Nils Vortmeier for many helpful suggestions on how to
improve a draft of this blog post.
[1] Guozhu Dong and Rodney W. Topor. Incremental evaluation of datalog queries. In ICDT 1992, pages 282–296. Springer, 1992.
[2] Guozhu Dong and Jianwen Su. First-order incremental evaluation of datalog queries. In Database Programming Languages, pages 295–308. Springer, 1993.
[3] Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199–209, 1997.
[4] Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. ArXiv 2015.
[5] Wouter Gelade, Marcel Marquardt, and Thomas Schwentick. The dynamic complexity of formal languages. ACM Trans. Comput. Log., 13(3):19, 2012.
[6] Thomas Zeume and Thomas Schwentick. On the quantifier-free dynamic complexity of Reachability. Inf. Comput. 240 (2015), pp. 108–129
[7] Thomas Zeume. The dynamic descriptive complexity of k-clique. In MFCS 2014, pages 547–558. Springer, 2014.
