Benjamin Rossman (M.I.T.)
will discuss a recent lower bound of Omega(n^(k/4)) on the size of depth-d
circuits for the k-clique problem on n-node graphs. This improves previous
lower bounds (e.g. Omega(n^(k/89d2)) [P. Beame '90]) by removing dependence
on d from the exponent of n. This result has an interesting corollary in
logic: it implies that the "bounded variable logics" FO1, FO2, ..., FO^k,
... (where FO^k consists of first-order sentences in which no subformula has
no more than k free variables) are increasingly expressive on ordered
graphs. It was previously an open question whether every first-order
property of ordered graphs could be defined by a sentence of FO3 (i.e.
using only three variables).