2006-2007 seminars

Jun
05
2007

Computer Science/Discrete Mathematics Seminar I

Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes
10:30am|S-101

The Fast Johnson-Lindenstrauss Transorm was recently discovered by Ailon and Chazelle as a technique for performing fast dimension reduction from $\ell_2^d$ to $\ell_2^k$ in time $O(\max\{d\log d, k^3\})$, where $k$ is the target lower dimension...

May
22
2007

Computer Science/Discrete Mathematics Seminar I

Expander Codes and Somewhat Euclidean Expllicit Sections
10:30am|West Building Lecture Theatre

This talk is devoted to linear subspaces of $R^N$ on which $\ell_1$ and $\ell_2$-norms are closed to each other (up to the obvious normalizing factor $N^{1/2}$). Such ``sections'' are important e.g. in the theory of metric embeddings, and for many...

May
17
2007

Computer Science/Discrete Mathematics Seminar II

Proof of the Parallel Repetition Theorem
10:45am|West Building Lecture Theatre, IAS

I will present Holenstein's (STOC 07) simplification of Raz's (STOC '95) proof of the parallel repetition theorem for two prover games. This theorem is a crucial component in many PCP constructions leading to tight hardness of approximation results...

May
14
2007

Computer Science/Discrete Mathematics Seminar I

Approximation Algorithms for Buy-at-Bulk Nework Design
Chandra Chekuri
11:15am|S-101

Buy-at-bulk network design problems arise in telecommunication networks and related fields where economies of scale result in concave cost functions for purchasing bandwidth. A basic problem in this area is the following. We are given a graph G=(V,E...

May
08
2007

Computer Science/Discrete Mathematics Seminar II

An Exponential Time/Space Speedup for Resolution
10:30am|S-101

This is joint work with Philipp Hertel Satisfiability algorithms have become one of the most practical and successful approaches for solving a variety of real-world problems, including hardware verification, experimental design, planning and...

May
07
2007

Computer Science/Discrete Mathematics Seminar I

Reachability Problems: An Update
Eric Allender
11:15am|S-101

We study the complexity of restricted versions of st-connectivity, which is the standard complete problem for NL. Grid graphs are a useful tool in this regard, since * reachability on grid graphs is logspace-equivalent to reachability in general...

May
01
2007

Computer Science/Discrete Mathematics Seminar II

One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications
10:30am|S-101

In this talk we study the one-way multi-party communication model, in which each of the k parties speaks exactly once in its turn. For every fixed k, we prove a tight lower bound of Omega(n^(1/(k-1))) on the probabilistic communication complexity of...

Apr
30
2007

Computer Science/Discrete Mathematics Seminar I

History of the Theory of Error-Correcting Codes
Elwyn Berlekamp
11:15am|S-101

This subject began in the late 1940s with the opus of Shannon [1948] and the short papers of Hamming [1950] and Golay [1949], followed a decade later by the powerful constructions of Bose-Chaudhuri-Hocquenghem and Reed-Solomon. A variety of...

Apr
24
2007

Computer Science/Discrete Mathematics Seminar II

Consensus Clustering, Hieraracical Clustering and Phylogeny
10:30am|S-101

Consensus clustering is the problem of aggregating a list of clusterings of ground data into one clustering. I will present new approximation algorithms for this problem, building on techniques used for ranking problems (described in my previous...

Apr
23
2007

Computer Science/Discrete Mathematics Seminar I

Disigning Efficient Program Checkers by Delegating Their Work
11:15am|S-101

Program checking, program self-correcting and program self-testing were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in the mid eighties as a new way to gain confidence in software, by considering program correctness on an input by...