Colloquium Details
Finding Needles in Exponential Haystacks
Speaker: Joel Spencer, CIMS
Location: Warren Weaver Hall 1302
Date: September 21, 2012, 11:30 a.m.
Host: Dennis Shasha
Synopsis:
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) No Outliers. Given $n$ vectors $r_j$ in $n$-space with all coefficients in $[-1,+1]$ one wants a vector $x=(x_1,...,x_n)$ with all $x_i=+1$ or $-1$ so that all dot products $x\cdot r_j$ are at most $K\sqrt{n}$ in absolute value, $K$ an absolute constant. A random $x$ would make $x\cdot r_j$ Gaussian but there would be outliers. The existence of such an $x$ was first shown by the speaker. The new approach, due to Lovett and Meka, is to begin with $x=(0,...,0)$ and let it float in kind of restricted Brownian Motion until all the coordinates hit the boundary.
(ii) 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 < 2^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 of the algorithm is unusual, connecting the running of the algorithm with certain Tetris patterns. [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.]
Speaker Bio:
Joel Spencer is a Professor of Computer Science and Mathematics at the Courant Institute. His research centers about The Probabilistic Method, the analysis of random structures and random algorithms.
Notes:
In-person attendance only available to those with active NYU ID cards.