Random Graphs, First-Order Logic, and AC^0 Circuits

• Yijia Chen
• Fudan University, Shanghai
• Homepage

First-order logic (FO) has very limited expressive power. One of the best-known examples is its 0-1 law on random graphs. Among others, it implies that FO cannot express PARITY. However, once the graphs are ordered, the 0-1 law completely breaks down. Thus, to prove FO cannot define PARITY on ordered graphs, one uses the remarkable machinery of Hastad's Switching Lemma on AC^0 circuits.

In 2008, Rossman proved that the k-clique problem cannot be defined by FO using only k/4 variables, resolving a long-standing open problem in finite model theory and complexity theory. His proof is built on a brilliant application of Hastad's Switching Lemma on ordered random graphs.

In the talk, I will explain our recent work extending Rossman's result to the so-called planted clique conjecture. Among others, it shows that any super-constant clique cannot be characterized by FO, even in case that the given ordered graphs have a huge planted clique.

This is joint work with Joerg Flum (Freiburg).