2009-2010 Seminars

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

We consider the following two questions: 1) Is the MAX-CUT problem hard on random geometric graphs of the type considered by Feige and Schechtman (2002)? 2) Is the value of a mathematical relaxation such as semi- definite programming (SDP) for a...

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

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

Sparse recovery problems arise in many applications. Suppose v is an unknown N-dimensional signal with at most k nonzero components. We call such signals k-sparse. Suppose we are able to collect n \ll N linear measurements of v , and wish to...

We consider the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most three variables. Since the all-zero assignment always satisfies all the equations exactly, we restrict the...

A locally decodable code (LDC) is an error correcting code that allows for probabilistic decoding of a single message bit by reading a corrupted encoding in a small number of locations. Until recently, the only LDC constructions known where based on...

*It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest. Each participant in a competitive economy is led by an invisible hand to promote an end which was no...

Intensive study throughout the last three decades has yielded a rigorous understanding of the spectral-gap of the Glauber dynamics for the Ising model on $Z^2$ everywhere except at criticality. While the critical behavior of the Ising model has long...

The cover time of a graph is one of the most basic and well-studied properties of the simple random walk, and yet a number of fundamental questions concerning cover times have remained open. We show that there is a deep connection between cover...