CMU Campus
Department of         Mathematical Sciences
Events People Colloquia and Seminars Conferences Centers Positions Areas of Research About the Department Alumni
Math Colloquium
Joel Spencer
New York University
Title: Finding Needles in Exponential Haystacks

Abstract: 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 \leq 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 (due to Don Knuth and others) 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 $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.

Date: Friday, April 12, 2013
Time: 4:30 pm
Location: Wean Hall 7500
Submitted by:  Loh