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.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math