# 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.

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:

68W20

Keywords: