[Colloquium] Talk by Benjamin Rossman, MIT on March 2, 2010

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Tuesday, March 2, 2010
Time: 3:00 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------------------

Speaker:	Benjamin Rossman

From:		MIT

Web page:	http://www.mit.edu/~brossman/

Title: Lower Bounds for k-CLIQUE on Random Graphs

Abstract: In this talk I will describe lower bounds of n^(k/4) on the average-case complexity of the k-CLIQUE problem (on Erdos-Renyi random graphs at the appropriate threshold) for two classes of circuits: AC^0 and monotone circuits.  These lower bounds use a similar technique, even though different combinatorial tools are required in the AC^0 and monotone settings.  Moreover, k/4 is tight (by results of Amano for AC^0 and the speaker for monotone).  I will also discuss a corollary of the AC^0 lower bound concerning first-order logic: we show that the number-of-variables hierarchy is strict in terms of expressive power on ordered graphs (i.e. for every k, there is a sentence involving k variables that is not equivalent on ordered graphs to any sentence involving k-1 variables).  Prior to this result, it was unknown whether 3 variables suffice to define any first-order property of ordered graphs.


Please note that refreshments will be prior to the talk at 2:30 in RY 255.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20100211/c878fc02/attachment.htm