Algorithms and Complexity Seminar

Random Graphs and First-order Logic with Parity Quantifiers

Swastik Kopparty (MIT)

The classical zero-one law for first-order logic on random graphs says that for any first-order sentence F in the theory of graphs, as n approaches infinity, the probability that the random graph G(n, p) satisfies F approaches either 0 or 1. In this work, we search for related phenomena for first order logic equipped with the parity quantifier, FO[parity]. Our main result is the following "modular convergence law":

For any FO[parity] sentence F, there are two rational numbers a_0, a_1, such that for i in {0,1}, as n approaches infinity, the probability that the random graph G(2n+i, p) satisfies F approaches a_i.

Our approach is based on multivariate polynomials over finite fields, in particular, on a new generalization of the Gowers norm. The proof generalizes the original quantifier elimination approach to the zero-one law, and has analogies with the Razborov-Smolensky method for lower bounds for AC0 with parity gates.

Along the way, we obtain examples of simple graph properties that are exponentially uncorrelated with any FO[parity] sentence. Our methods also enable us to determine (upto small error terms) the joint distribution of the number of copies (mod m) in the random graph G(n,p), of all graphs of bounded size.

No background in logic will be assumed.

Joint work with Phokion Kolaitis (IBM Almaden).