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
Abstract:
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/