Avoiding Outliers

Given n vectors rj in n-space with all coefficients in [−1,+1] one wants a vector x=(x1,…,xn) with all xi=+1 or −1 so that all dot products x⋅rj are at most Kn‾√ in absolute value, K an absolute constant. A random x would make x⋅rj roughly Gaussian but there would be outliers. The existence of such an x was first shown by the speaker, resolving a discrepancy question of Paul Erdős. However, the original argument did not give an effective algorithm. The first algorithm was found by Nikhil Bansal. The approach here, due to Lovett and Meka, is to begin with x=(0,…,0) and let it float in a kind of restricted Brownian Motion until all the coordinates hit the boundary. There is some nice probability using multidimensional Gaussians, together with a martingale result on a “Gaussian Casino.”
Paul Erdős was an extraordinary twentieth century mathematician with a unique life style and the speaker will include personal reminiscences of him.