Applied Mathematics Colloquium

  We discuss two recent methods in which an object   with a certain property is sought. In both, using of   a straightforward random object would succeed with   only exponentially small probability. The new   randomized algorithms run efficiently and also   give new proofs of the existence of the desired   object. In both cases there is a potentially broad   use of the methodology.     

  (i) Consider an instance of k-SAT in which each clause   overlaps (has a variable in common, regardless of the negation   symbol) with at most d others. Lovasz showed that when   ed < 2k (regardless of the number of variables) the   conjunction of the clauses was satisfiable. The new approach   due to Moser is to start with a random true-false assignment.   In a WHILE loop, if any clause is not satisfied, we "fix it"   by a random reassignment. The analysis of the algorithm is   unusual, connecting the running of the algorithm with certain   Tetris patterns, and leading to some algebraic combinatorics.  [These results apply in a quite general setting   with underlying independent "coin flips" and bad events (the   clause not being satisfied) that depend on only a few of the   coin flips.]     

  (ii) No 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 K√n   in absolute value, K an absolute constant. A random   x would make x·rj Gaussian but there would   be outliers. The existence of such an x was first shown   by the speaker.  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.