Revision #2 Authors: Albert Atserias, Anuj Dawar

Accepted on: 25th June 2013 14:45

Downloads: 179

Keywords:

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 degree of the polynomials

that is a tower of exponentials of height as large as the nesting

depth of parity quantifiers in the formula. We show that this

tower-type dependence on the depth of the formula is necessary. We

build a family of formulas of depth $q$ whose approximating

polynomials must have degree bounded from below by a tower of

exponentials of height proportional to $q$. Our proof has two main

parts. First, we adapt and extend the results by Kolaitis and Kopparty that describe the joint

distribution of the parity of the number of copies of small subgraphs

on a random graph to the setting of graphs of growing size. Secondly,

we analyse a variant of Karp's graph canonical labelling algorithm and

exploit its massive parallelism to get a formula of low depth that

defines an almost canonical pre-order on a random graph.

More details were added to the proof of Lemma 3.

Revision #1 Authors: Albert Atserias, Anuj Dawar

Accepted on: 2nd October 2012 14:20

Downloads: 277

Keywords:

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 bounds the degree of the polynomials by a tower of exponentials in the nesting depth of parity quantifiers in the formula. We show that this tower-type dependence is necessary. We build a family of formulas of depth $q$ whose approximating polynomials must have degree bounded from below by a tower of exponentials of height proportional to $q$. Our proof has two main parts. First, we adapt and extend known results describing the joint distribution of the parity of the number of copies of small subgraphs on a random graph to the setting of graphs of growing size. Second, we analyse a variant of Karp's graph canonical labeling algorithm and exploit its massive parallelism to get a formula of low depth that defines an almost canonical pre-order on a random graph.

TR12-015 Authors: Albert Atserias, Anuj Dawar

Publication: 23rd February 2012 09:34

Downloads: 551

Keywords:

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 degree of the polynomials

that is a tower of exponentials of height as large as the nesting

depth of parity quantifiers in the formula. We show that this

tower-type dependence on the depth of the formula is necessary. We

build a family of formulas of depth $q$ whose approximating

polynomials must have degree bounded from below by a tower of

exponentials of height proportional to $q$. Our proof has two main

parts. First, we adapt and extend known results describing the joint

distribution of the parity of the number of copies of small subgraphs

on a random graph to the setting of graphs of growing size. Secondly,

we analyse a variant of Karp's graph canonical labelling algorithm and

exploit its massive parallelism to get a formula of low depth that

defines an almost canonical pre-order on a random graph.