2006-2007 seminars

Mar
13
2007

Computer Science/Discrete Mathematics Seminar II

The Design and Analysis of Simple Algorithms (for Search and Optimization)
11:30am|S-101

The "Design and Analysis of Algorithms" or "Introduction to Algorithms" is a basic undergraduate course in CS. In such courses, the organizational theme is often in terms of "basic algorithmic paradigms" such as greedy algorithms, dynamic...

Mar
12
2007

Computer Science/Discrete Mathematics Seminar I

Disjoint Paths in Networks
Sanjeev Khanna
12:15pm|S-101

A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a network and a collection of source-destination pairs in the network. The goal is to maximize the number of pairs that can be connected by...

Mar
06
2007

Computer Science/Discrete Mathematics Seminar II

A Product Theorem in Free Groups (Continued)
10:30am|S-101

We will continue the proof of the following result: if A is a finite subset of a free group with at least two non-commuting elements then |AAA| is almost quadratic in |A|. Last week we reduced the problem to obtaining lower bounds on |ABC| when...

Mar
05
2007

Computer Science/Discrete Mathematics Seminar I

Efficient Algorithms Using the Multiplicative Weights Update Method
Satyen Kale
11:15am|S-101

Algorithms based on convex optimization, especially linear and semidefinite programming, are ubiquitous in Computer Science. While there are polynomial time algorithms known to solve such problems, quite often the running time of these algorithms is...

Feb
26
2007

Computer Science/Discrete Mathematics Seminar I

Hardness Amplification for Errorless Heuristics
11:15am|S-101

We say a problem is tractable on average if it can be solved on a "good" fraction of instances by an efficient algorithm. To make this definition precise, we need to make two choices: First, what is a "good" fraction of instances - is it 1%, 51%, 99...

Feb
20
2007

Computer Science/Discrete Mathematics Seminar II

Algebraic Property Testing - Part II
10:30am|S-101

A Property P of functions is said to be locally testable if there exists a probabilistic algorithm that makes few (constant) queries for the value of f and accepts those satisfying P while rejecting functions that are far from any function...

Feb
19
2007

Computer Science/Discrete Mathematics Seminar I

Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes
11:15am|S-101

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are...

Feb
13
2007

Computer Science/Discrete Mathematics Seminar II

Fast Johnson-Lindenstrauss Transform(s)
10:30am|S-101

A classic functional analytic result by Johnson and Lindenstrauss from 1984 implies that any Euclidean metric on n points can be represented using only k=(log n)/epsilon^2 dimensions with distortion epsilon. In computer science, this result has been...

Feb
12
2007

Computer Science/Discrete Mathematics Seminar I

Biased Positional Games and Thin Hypergraphs with Large Covers
11:15am|S-101

We consider biased positional games, played on the edge set of a complete graph Kn on n vertices. These games are played by two players, called Maker and Breaker, who take turns in claiming previously unoccupied edges of Kn. Maker claims a single...