Events — Colloquia & Seminars
The Constant-Depth Complexity of k-Clique
Speaker: Benjamin Rossman, MIT
Date: Friday, December 12, 2008
Talk: 4:00 PM, 366 WVH
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).
Brief Biography
none provided