Finding Needles in Exponential Haystacks

Thursday, September 11, 2014 - 9:00am - 9:50am
Keller 3-180
Joel Spencer (New York University)
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 for certain
d,k (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 (due, basically, to
Don Knuth) 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 n-space
with all coefficients between -1 and +1 one wants a
vector x with all coordinates -1 or +1 so
that its dot products with all the n vectors are at
most K times the square root of n
in absolute value, K an absolute constant. A random
x would make the dot product 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 the all zero vector and let it float in a kind
of restricted Brownian Motion until all the coordinates hit
the boundary.
MSC Code: