Colloquium Details
Theory Day
Speaker:
Location: Warren Weaver Hall 109
Date: November 16, 2001, 9:30 a.m.
Host: Yevgeniy Dodis
Synopsis:
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.
Abstract
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
Abstract
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.
Abstract
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.
Abstract
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.
Notes:
In-person attendance only available to those with active NYU ID cards.