The Taub Faculty of Computer Science Events and Talks

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