Theory Seminar: The Constant-Depth Complexity of k-Clique

בנג'מין רוסמן (M.I.T.)
יום ראשון, 13.7.2008, 11:00
חדר 337, בניין טאוב למדעי המחשב

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

בחזרה לאינדקס האירועים