Title: Random graphs and the parity quantifier
Speaker: Swastik Kopparty, CSAIL, MIT
Date: Wednesday, September 15, 2010 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
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, the probability that the random graph G(n, p) satisfies F approaches either 0 or 1 as n grows. It is well known that this law fails to hold for properties involving parity phenomena (oddness/evenness): for certain properties, the probability that G(n, p) satisfies the property need not converge, and for others the limit may be strictly between 0 and 1.
In this talk, I will discuss the behavior of FO[parity], first order logic equipped with the parity quantifier, on random graphs. Our main result is a "modular convergence law" which precisely captures the behavior of FO[parity] properties on large random graphs. This in turn helps us find explicit hard functions and pseudorandom generators against FO[parity] properties.
I will give an overview of these results and their proofs. Along the way, we will study some basic and natural questions about the distribution of subgraph counts *mod 2* in random graphs (what is the probability that G(n,p) has: an odd number of triangles? an even number of 4-cycles? an odd number of triangles and an even number of 4-cycles? etc.). The proofs generalize the original quantifier elimination approach to the zero-one law, and have analogies with the Razborov-Smolensky method for lower bounds on AC^0 with parity gates.
Joint work with Phokion Kolaitis.