## Computer Science and Discrete Mathematics

Theoretical Computer Science and Discrete Mathematics

## Approximating the Longest Increasing Subsequence in Polylogarithmic Time

Michael Saks
Rutgers, The State University of New Jersey
October 12, 2010 - 10:30am

Finding the longest increasing subsequence (LIS) is a classic algorithmic problem. Simple O(n log n) algorithms, based on dynamic programming, are known for solving this problem exactly on arrays of length n.

## Subsampling Mathematical Relaxations and Average-case Complexity

Boaz Barak
May 24, 2010 - 11:15am

We consider the following two questions:

## Reductions Between Expansion Problems

May 18, 2010 - 10:30am

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:

## The Stepanov Method

Avi Wigderson
May 25, 2010 - 10:30am

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.

## Small-Bias Sets

Amir Yehudayoff
May 11, 2010 - 10:30am

An epsilon-biased set X in {0,1}n is a set so that for every non-empty set T in [n] the following holds. The random bit B(T) obtained by selecting at random a vector x in X, and computing the mod-2 sum of its T-coordinates, has bias at most epsilon. Such sets may be viewed as generating matrices of binary error correcting codes of distance (1/2 - epsilon), as well as pseudorandom sets in the sense that all their nontrivial Fourier coefficients are at most epsilon in absolute value.

## CSDM - Dependent Random Choice and Approximate Sidorenko's Conjecture

Benny Sudakov
University of California at Los Angeles
September 20, 2010 - 11:15am

A beautiful conjecture of Erd\H{o}s-Simonovits and Sidorenko states that if H is a bipartite graph, then the random graph with edge density p has in expectation asymptotically the minimum number of copies of H over all graphs of the same order and edge density. This conjecture also has an equivalent analytic form and has connections to a broad range of topics, such as matrix theory, Markov chains, graph limits, and quasirandomness.

## PMSP - Quasi-random boolean functions, and inapproximability

Ryan O'Donnell
Carnegie Mellon University
June 17, 2010 - 11:15am

## PMSP - Quasi-random graphs and hypergraphs

Fan Chung Graham
UC San Diego
June 16, 2010 - 11:15am

## PMSP - Random-like behavior in deterministic systems

Benjamin Weiss
Einstein Institute of Math, Hebrew University
June 16, 2010 - 4:00pm

## PMSP - Pseudorandomness of the Mobius function

Peter Sarnak
Princeton University and Institute for Advanced Study
June 18, 2010 - 4:00pm