Computer Science Department

Computer Science Colloquium
bar

Program

9:30 - 10:00 Coffee and Bagels

10:00 a.m. - 10:55 a.m.

Learning a Hidden Matching

Prof. Noga Alon

10:55 - 11:05 Short Break

11:05 a.m. - 12:00 a.m.

From the Tennis Club to the Golf Course in .005 seconds or Less: a Commercial Shortest-Path Engine That Employs Preprocessing

Prof. Phil Klein

12:00 - 2:00 Lunch Break

2:00 p.m. - 2:55 p.m.

The Quickest Multicommodity Flow Problem (or Techniques for Flows Over Time)

Prof. Lisa Fleischer

2:55 - 3:15 Coffee Break

3:15 - 4:10

Linear Time Encodable/Decodable Codes with Near-Optimal Rate

Dr. Venkatesan Guruswami

THEORY DAY - Friday, April 19, 2002

New York University
Room 109 Warren Weaver Hall
251 Mercer Street
New York, NY 10012-1185

The IBM Research|NYU|Columbia Theory Day is a semi-annual conference aimed to bring together people in New York Metropolitan area for one day of interaction and discussion. The Theory Day features several (usually 4-5) hour-long presentations by leading theoretical computer scientists about state-of-the-art advances in various areas. Some presentations give a survey of the latest advances in some area, while others may concentrate on a particular (often ground-breaking!) result. The meeting is free and open to everyone; in particular, students are encouraged to attend.

Itinerary

Coffee and bagels - 9:30 a.m. - 10:00 a.m.

10:00 a.m. - 10:55 a.m.

Learning a Hidden Matching

Prof. Noga Alon
Tel Aviv University and IAS Princeton

Abstract

We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an edge. This is motivated by a problem that arises in molecular biology. In the deterministic non-adaptive setting, we prove a (0.25+o(1))n^2 upper bound and a nearly matching 0.16 n^2 lower bound for the minimum possible number of required queries. In contrast, if we allow randomness then we obtain (by a randomized, non-adaptive algorithm) a much lower O(n \log n) upper bound, which is best possible (even for randomized fully adaptive algorithms).

Joint work with R. Beigel, S. Kasif, S. Rudich and B. Sudakov

SHORT BREAK - 10:55 a.m. - 11:05 a.m.

11:05 a.m. - 12:00 a.m.

From the Tennis Club to the Golf Course in .005 seconds or Less: a Commercial Shortest-Path Engine That Employs Preprocessing

Prof. Phil Klein
Brown University and WaveMarket

Abstract

As part of a software suite for supporting location-based services, WaveMarket has developed a fast engine for computing a single-source, single-sink shortest path in a road network. The engine is faster than competing products by more than an order of magnitude. In this talk, we describe some of the the algorithmic ideas behind this advance.

Lunch break - 12:00 noon - 2:00 p.m.

2:00 p.m. - 2:55 p.m.

The Quickest Multicommodity Flow Problem (or Techniques for Flows Over Time)

Prof. Lisa Fleischer
CMU

Abstract

Standard network flows capture many aspects of routing problems but miss one crucial element: flows occur over time. Ford and Fulkerson recognized this omission when they introduced flows over time. In this model, there is a transit time, or delay, associated with each arc to address the fact that flow does not travel instantaneously across the arc. Now, given a time bound, it is possible to consider the flow-over-time equivalents of standard network flow problems. This allows for more accurate modelling of problems in telecommunications, transportation, financial planning, manufacturing, and logistics.

Ford and Fulkerson showed how to solve the maximum flow over time problem by reducing it to a minimum cost flow problem. However, the minimum cost flow over time problem is already NP-hard. And, the obvious linear program formulation of the multicommodity flow over time problem depends linearly on the time bound, so is in general not of polynomial size. Thus, problems in flows over time are inherently more difficult than the standard flow problems.

We will introduce flows over time, review some of the classical results, and describe a newly devised FPAS for both the multicommodity flow over time problem and the same problem with costs that is joint work with Martin Skutella. Time permitting we may touch upon further extensions.

Coffee break - 2:55 noon - 3:15 p.m.

3:15 - 4:10

Linear Time Encodable/Decodable Codes with Near-Optimal Rate

Dr. Venkatesan Guruswami
University of California, Berkeley

Abstract

We present a simple, explicit construction of error-correcting codes that have a near-optimal rate vs. error-correction trade-off and are encodable and decodable in linear time. Formally, we construct, for every $r$ ($0 < r < 1$), a family of codes of rate $r$ that can be encoded in linear time and decoded in linear time from up to a fraction $(1-r-\epsilon)/2$ of errors, for arbitrary $\epsilon > 0$. The codes are defined over a fixed alphabet whose size depends only on $\epsilon$. These codes nearly match the ``Singleton bound'' and thus their rate vs. error-correction trade-off is essentially optimal, and so is their encoding/decoding time (up to constant factors). Previously known codes over a constant-sized alphabet that approached the Singleton bound (eg. certain algebraic-geometric codes) suffered from complicated constructions and/or high (certainly, super-linear) encoding/decoding complexity.

Concatenating these codes with a suitable inner code of constant size yields constructions of linear time encodable/decodable binary codes that match the so-called ``Zyablov bound'' (the best rate vs. distance trade-off known for explicit binary codes with reasonable decoding complexity), for the entire range of error fractions. In contrast, previously known linear-time binary codes, due to (Spielman, 1996), could only correct a very small fraction (about $10^{-6}$) of errors.

Our approach is to first construct, by adapting techniques from a recent work of (Zemor, 2001), certain high rate linear-time codes that can correct a small fraction of errors, and then to increase the error-resilience using expanders akin to an approach used for erasure codes by (Alon, Edmonds, Luby, 1995).

Joint work with Piotr Indyk (MIT).

Details

The Theory Day is held at Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, Auditorium 109, New York.

For directions, please see http://www.cims.nyu.edu/direct.html and http://cs.nyu.edu/csweb/Location/directions.html (building 46)

To subscribe to our mailing list, follow instructions at http://www.cs.nyu.edu/mailman/listinfo/theory-ny

Hosts:
Yevgeniy Dodis dodis@cs.nyu.edu, (212) 998-3084
Tal Rabin talr@watson.ibm.com
Baruch Schieber sbar@watson.ibm.com

Colloquium Information: http://cs.nyu.edu/csweb/Calendar/colloquium/index.html

bar
e-mail: webmaster@cs.nyu.edu