# 2009-2010 Seminars

May

25

2010

### Computer Science/Discrete Mathematics Seminar II

The Stepanov Method

10:30am|West Bldg. Lecture Hall

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

May

24

2010

### Computer Science/Discrete Mathematics Seminar I

Subsampling Mathematical Relaxations and Average-case Complexity

11:15am|S-101

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

May

18

2010

### Computer Science/Discrete Mathematics Seminar II

Reductions Between Expansion Problems

10:30am|West Bldg. Lecture Hall

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

May

11

2010

### Computer Science/Discrete Mathematics Seminar II

Small-Bias Sets

10:30am|S-101

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

May

04

2010

### Computer Science/Discrete Mathematics Seminar II

Explicit Construction of RIP Matrices, Matrices With Small Coherence, and Related Problems

10:30am|S-101

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

Apr

27

2010

### Computer Science/Discrete Mathematics Seminar II

Hardness of Approximately Solving Linear Equations Over Reals

10:30am|S-101

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

Apr

20

2010

### Computer Science/Discrete Mathematics Seminar II

Matching Vector Codes

10:30am|S-101

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

Apr

19

2010

### Computer Science/Discrete Mathematics Seminar I

Can Complexity Theory Ratify the Invisible Hand of the Market?

Vijay Vazirani

11:15am|S-101

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

Apr

13

2010

### Computer Science/Discrete Mathematics Seminar II

Critical Slowdown for the Ising Model on the Two-Dimensional Lattice

Eyal Lubetzky

10:30am|S-101

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

Apr

12

2010

### Computer Science/Discrete Mathematics Seminar I

Cover Times, Blanket Times, and Majorizing Measures

11:15am|S-101

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