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).