##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Mikhail Alekhnovich

#### UCSD

## Random walk for satisfiability: the geometric point of view

##### Abstract:

Satisfiability is a canonical NP-complete problem that requires to find a $0$-$1$ satisfying assignment for a given set of Boolean constraints. I will consider the Random Walk algorithm that heuristically tries to find a solution by the random walk in the Boolean hypercube, that converges to a satisfying assignment. I will prove the linear upper bound for the expected number of steps of the walk for the class of random small density $3$-SAT formulas. This convergence follows the from geometric investigation of the convex hull of n randomly chosen points in the space.

Host: Jeff Remmel

### November 1, 2005

### 3:00 PM

### AP&M 7321

****************************