## PMSP - Regularity Lemmas in graph theory, additive combinatorics and TCS II

## Workshop on Pseudorandomness in Mathematical Structures

June 14 - 18, 2010

Organizers: Jean Bourgain, Russell Impagliazzo, Peter Sarnak and Avi Wigderson

Workshop Homepage:http://www.math.ias.edu/pseudo2010

Program: http://www.math.ias.edu/pseudo2010/program.

## PMSP - Approximate algebraic structure (groups, fields, homomorphisms, ...) I

## PMSP - Approximate algebraic structure (groups, fields, homomorphisms, ...) II

## PMSP - Computational pseudo-randomness and extractors I

## PMSP - Computational pseudo-randomness and extractors II

## The Stepanov Method

The Stepanov method is an elementary method for proving bounds on the number of roots of polynomials. At its core is the following idea. To upper bound the number of roots of a polynomial f(x) in a field, one sets up an auxiliary polynomial F(x) , of (magically) low degree, which vanishes at the roots of f with high multiplicity. That appropriate F exits is usually proved by a dimension argument.

## Subsampling Mathematical Relaxations and Average-case Complexity

We consider the following two questions:

## Reductions Between Expansion Problems

The small-set expansion conjecture introduced by Raghavendra and Steuerer is a natural hardness assumption concerning the problem of approximating edge expansion of small sets (of size $\delta n$) in graphs. It was shown to be intimately connected to the well-known Unique Games Conjecture.

Pursuing this line of research further, we obtain the following results: