Rutgers Discrete Mathematics Seminar

Title: Strong Noise Sensitivity and Random Graphs

Speaker: Eyal Lubetzky, NYU

Date: Monday, April 25, 2016 2:00 pm

Location: Hill center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ


The notion of noise sensitivity of a Boolean function, introduced in the seminal work of Benjamini, Kalai and Schramm (1999), describes its likelihood to flip under small perturbations of its input. We study noise sensitivity and a natural stronger version of it, addressing the effect of noise given a specific witness in the original input. Our main context is the Erdos-Renyi random graph, where already the property of containing a given graph is sufficiently rich to separate these notions. In particular, our analysis implies (strong) noise sensitivity in settings where the Benjamini-Kalai-Schramm criterion involving the first Fourier level does not apply, e.g., when the threshold goes to 0 as a power of the number of variables. ‚Äč

Joint work with Jeff Steif.