Computer Science Department

Computer Science Colloquium

THEORY DAY - Friday, November 16, 2001

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

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

Expander Graphs - Where Combinatorics and Algebra Compete and Cooperate

Prof. Avi Wigderson
IAS Princeton and the Hebrew University

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


Expansion of graphs can be given equivalent definitions in combinatorial and algebraic terms. This is the most basic connection between combinatorics and algebra illuminated by expanders and the quest to construct them. The talk will survey how fertile this connection has been to both fields, focusing on recent results.

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

Pattern Discovery in Computational Biology

Dr. Laxmi Parida
IBM Research

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


Given a string, a pattern is a repeating substring possibly with some "dont care" characters. The problem of pattern discovery is that of finding all such substrings that appear at least $k$ times. Discovering such patterns in nucleic and amino acid sequences is of great interest in computational biology. If we do not have a model for evaluating the significance of the patterns a priori, it is important that all the patterns be detected. However, the number of such patterns could be exponential in the size of the input. In this talk, I will describe a notion of redundancy which gives rise to a provably small number of irredundant patterns, while preserving the information content of the set of all patterns. I will further discuss how this helps in designing a very efficient pattern discovery algorithm. There are several generalizations of the pattern discovery problem which are important in computational biology and we will discuss one such generalization. We will conclude the talk by presenting several concrete examples, of the application of pattern discovery in the area of biology.

LUNCH BREAK - 12:00 noon - 2:00 p.m.

Algorithms for Minimizing Weighted Flow Time

Prof. Sanjeev Khanna
CIS, University of Pennsylvania

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


We consider the following classical scheduling problem. Jobs arrive over time to be scheduled on a single machine. Each job has a processing time and a weight. We seek to minimize the sum of weighted flow times of the jobs. The flow time of a job is the overall time the job spends in the system from the time it arrives to the time its processing is completed. We allow preemption of jobs. The algorithm that at any time schedules the job with shortest remaining processing time (SRPT) is known to be optimal when all jobs have the same weight. However, no algorithms with sub-polynomial approximation ratios were known for the weighted problem. We present new on-line and off-line algorithms for the weighted problem that give much improved performance ratios and strongly suggest the possibility of an approximation scheme (ptas) for this problem. This is based on joint work with Chandra Chekuri and An Zhu.

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

Building Uniform Subtrees of a Cayley Tree

Dr. Peter Winkler
Bell Labs

3:15 p.m. - 4:10 p.m.


Sampling uniformly at random from a set of combinatorial objects is now well known to be useful in approximation algorithms. Sampling can also tell us much about the objects themselves, especially when the sampling method has nice properties and lends itself to analysis. When the objects in question are equipped with notions of size and containment, it is natural to look for a sampling algorithm which builds objects one step at a time, in such a way that at the nth step we get a uniformly random object of size n. With Malwina Luczak (U. of Cambridge), we prove the existence of, and describe, such a process for subtrees of a Cayley tree.

Yevgeniy Dodis, (212)998-3084
Colloquium Information: