Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: The Constant-Depth Complexity of k-Clique
event speaker icon
Benjamin Rossman (M.I.T.)
event date icon
Sunday, 13.07.2008, 11:00
event location icon
Room 337-8 Taub Bld.
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).