Ankündigung Vortrag

Im Rahmen des Kolloquiums des Instituts für Informatik hält

Herr Benjamin Rossman (Tokyo Institute of Technology)
am Dienstag, den 05.03.13 um 16:00 Uhr,
in Seminarraum 307 (Robert-Mayer-Str 11-15, 3.OG)

einen Vortrag zum Thema

Average-case complexity of detecting cliques

Erdos-Renyi random graphs are believed to be a source of hard instances for clique problems.  While the random graph G(n,1/2) almost surely contains cliques of size ~2*log(n), Karp in 1976 conjectured that no polynomial-time algorithm finds a clique larger than (1+epsilon)*log(n). As a tiny step toward this conjecture, we show (tight) lower bounds on the average-case complexity of the k-clique problem in two well-studied classes of circuits: bounded-depth (AC^0) circuits and monotone circuits. As a corollary, we obtain the first "size hierarchy" theorem for AC^0 and a related result for first-order logic.

Es lädt ein: Prof. N. Schweikardt

Zusätzliche Informationen