Applied Mathematics Colloquium
Monday
March 3, 2014
4:15 PM
Finding Needles in Exponential Haystacks
Speaker:
Joel Spencer,
Computer Science and Mathematics,
New York University
Location:
Annenberg 105
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.
(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.
Series
Applied Mathematics Colloquium Series
Contact: Sydney Garstang at x4555 sydney@caltech.edu