期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2012
卷号：2012
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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−(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.
关键词：finite model theory, low-degree polynomials, random graphs, Zero-one laws
