##### Department of Mathematics,

University of California San Diego

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

### New Faculty Colloquium

## Misha Alekhnovich

#### UCSD

## What makes the search problem computationally hard?

##### Abstract:

In this general talk I will discuss the complexity of NP-complete combinatorial search problems for several computational models, such as DPLL algorithms, Greedy algorithms, Linear and Semidefinite relaxations. I will survey several lower bounds for these models and discuss how the expansion of the underlying graph affects the computational intractability of the search problem.

Host:

### February 23, 2006

### 12:00 PM

### AP&M 7321

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