DIMACS Theoretical Computer Science Seminar

Title: Monotone Lower Bounds via Fourier Analysis

Speaker: Siu Man Chan, Princeton University

Date: Wednesday, March 12, 2014 11:00-12:00pm

Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ


We will discuss lower bounds on combinatorial models of computation under monotone restrictions, using the Fourier analysis techniques introduced by Potechin. We will prove tight size bounds on monotone switching networks for the NP-complete problem of k-clique, and (if time permits) for an explicit monotone problem by connecting the P-complete problem of generation with reversible pebble games. The latter result gives alternative proofs of the separations of m-NC from m-P and of m-NC^i from m-NC^{i+1} , different from RazMcKenzie (Combinatorica '99).

See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/