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.

I appreciate this post -- it is a nice application.

ReplyDeleteI'd like to comment on the title, though. I think this blog would be more inviting if it used fewer unnecessary abbreviations. "App of Ramsey Thy to Dyn Desc Comp." just doesn't make me think the post is going to be accessible as this blog usually is. And if there's a typo (sadly not uncommon), then it makes error recovery for the reader much harder.