Rutgers Discrete Mathematics Seminar

Title: On a Resilience Version of The Littlewood-Offord Problem

Speaker: Asaf Ferber, MIT

Date: Monday, October 10, 2016 2:00 pm

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


In this talk we consider a resilience version of the classical Littlewood-Offord problem. That is, consider the sum X=a_1x_1+...a_nx_n, where the a_i-s are non-zero reals and x_i-s are i.i.d. random variables with P(x_1=1)=P(x_1=-1)=1/2. Motivated by some problems from random matrices, we consider the question: how many of the x_i-s can we typically allow an adversary to change without making X=0? We solve this problem up to a constant factor and present a few interesting open problems. Joint with: Afonso Bandeira (NYU) and Matthew Kwan (ETH, Zurich).