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 programming (SDP) for a...

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

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