Rossman’s clique result

6 December 2009

Rossman’s clique result

Filed under: Commentary — András Salamon @ 19:41
Tags: papers

This is about three of the major results Benjamin Rossman has published to date. The first one was showing that existential positive sentences are preserved by homomorphisms, over finite structures. The second was work with Dawar and Richerby, showing that Choiceless Polynomial Time is enough to separate P from the class expressible by IFP with counting.

I here discuss the third result, from STOC 2008. This gives a superpolynomial lower bound on the size of constant-depth circuits that decide CLIQUE.

Let $k$ be a constant. Rossman’s paper shows that for every $l > k$ , no constant-depth circuits of size $O(n^{k/4})$ distinguish between the graphs that contain an $l$ -clique and those that contain no $k$ -clique. This gives an $\omega(n^{k/4})$ lower bound on the size of constant-depth circuits for deciding $k$ -CLIQUE on $n$ -vertex graphs.

The corollary is that the bounded variable fragments of first-order logic over finite ordered graphs form a strict hierarchy. It was previously not known if even $FO^3$ was less expressive than $FO$ , on finite ordered graphs.

A logic over ordered structures has the built-in relation symbol $<$ between elements; the paper works with such logics.

Finite ordered graphs are important because for actual computation, we typically order the vertices, then compute over the resulting ordered structure. So there are many possible realisations of the same underlying unordered graph, one for each permutation of the vertices. The ordering of the vertices carries additional information, and this often does have a big impact in implementations. It then seems a priori not out the question that the 3-variable fragment of $FO$ over finite ordered graphs could be as expressive as $FO$ .

Note that the class of graphs can be turned into a set by taking each canonical $n$ -vertex graph in the equivalence class up to isomorphism as the one defined over vertices $\{1,2,\ldots,n\}$ .

Now for the technical ingredient.

By “size- $n$ graph property” I mean a function from the set of $n$ -vertex graphs to $\{0,1\}$ . Examples of size- $n$ graph properties are “is a connected graph”, “contains a $(\log n)$ -clique”, and “can be turned into a Hamiltonian cycle by adding or deleting at most $k$ edges”.

Let $f_n$ be a sequence of graph properties which can be represented as
constant depth circuits of size $O(n^t)$ for constant $t > 1/2$ . Let $k$ (a positive integer) and $\alpha$ (positive but less than $1/(2t-1)$ ) be constants. For every $n$ , let $G_n$ be an Erdős-Rényi random graph with $n$ vertices and edge probability $n^{-\alpha}$ , let $A_n$ be a uniform random set of $k$ vertices of $G_n$ (i.e. chosen uniformly from the $k$ -element subsets of $\{1,2,\ldots,n\}$ ), and let $H_n$ be the graph formed by adding all edges between the vertices in $A_n$ to $G_n$ .

Then $f_n(G_n) = f_n(H_n)$ asymptotically almost surely.

My paraphrase: for almost all graphs from the “right” range of edge densities, constant depth circuits of at most polynomial size cannot distinguish between general instances and those guaranteed to have a $k$ -clique.

Note that Lemma 2.1 ensures that when the edge density is in the “right” range, then there will tend to be few cliques. Hence forcing a $k$ -clique will in the limit be a non-null operation.

Note that “has a $k$ -clique” is a monadic second-order property, but zero-one laws do not hold for many quite weak fragments of MSO. Also, as noted by Matula in 1972, the size of the largest clique in $G_n$ is almost surely $O(\log n)$ if $\alpha$ is not fixed but instead varies so that $n^{-\alpha}$ is constant. As $n$ grows, while $k$ is fixed, $G_n$ is almost surely going to have a $k$ -clique with this model. Hence the choice of the random graph model is quite important.

The remark just before Lemma 2.1 mentions that the expectation of the
number of $k$ -cliques in $G_n$ is greater than 1. So in many cases there will already be a $k$ -clique in $G_n$ before another one is added. Much of the paper, including the machinery on $s$ -bounded clique-sensitive
cores (which is explained further in a note), then seems devoted to addressing this difficulty. I have not taken the time to fully grasp how the technical lemmas work together to resolve the niggling doubt one may have at this point, that a circuit designed for deciding the presence of a $k$ -clique should not necessarily be expected to distinguish between a graph that quite likely already has a $k$ -clique, from a graph that has had one added on.

In the meantime, I look forward to a journal version with (hopefully) a simpler proof.

Quite recently Rossman has written a paper which extends this result from constant-depth to monotone circuits. This is the first average-case lower bound result for this framework. An upper bound is also presented, based on Amano’s upper bound for constant depth circuits (submitted version).

(Edit 20100704: Benjamin has now replaced the link above with a one-page abstract. Presumably we’ll just have to wait until after FOCS 2010…)

Comments (2)

2 Comments »

[…] Last year I mentioned Benjamin Rossman’s monotone complexity result for k-CLIQUE. […]

Pingback by FOCS 2010 accepted papers « Constraints — 5 July 2010 @ 1:38 | Reply
[…] Benjamin Rossman showed an exponential size lower bound for fixed-depth circuits in 2008, in a breakthrough result. It is good to see continued progress in circuit lower bounds. In particular, Ryan Williams showed that NTIME[2n] does not have non-uniform ACC circuits of polynomial size, and also showed that there are languages in ENP that do not have non-uniform ACC circuits of subexponential size. (Note that it is still possible that allowing unbounded depth might allow subexponential size circuits). Perhaps these techniques can be extended to separate Note that this separates EXPNP and AC0[6]. This is was a long-standing open problem that would be one of the “small” consequences of proving P ≠ NP, and is was therefore seen as an important step in such a proof. […]

Pingback by New ACC circuit lower bounds « Constraints — 10 November 2010 @ 11:07 | Reply

RSS feed for comments on this post. TrackBack URI

Constraints

6 December 2009