Applied Mathematics Colloquium
Finding Needles in Exponential Haystacks
(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.
Contact: Sydney Garstang at x4555 email@example.com