[Colloq] Talk: Benjamin Rossman, MIT, Friday Dec. 12

[Rachel Kalweit]

TALK - Dec 12, 4 PM,366 West Vilage H

SPEAKER: Benjamin Rossman, MIT

Title: The Constant-Depth Complexity of k-Clique

ABSTRACT: I will discuss a recent AC0 lower bound:
the k-clique problem on graphs of size n cannot be
solved by constant-depth circuits of size
O(n^(k/4)). This result has an interesting
corollary in logic (finite model theory): the
first-order "variable hierarchy" is strict in
terms of expressive power on ordered graphs (it
was previously open whether 3 variables suffice to
define every first-order property of ordered graphs).