The IBM Research*NYU*Columbia Theory Day
                           Friday, November 16, 2001

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

                                  Program

 9:30  - 10:00    Coffee and bagels

10:00  - 10:55    Prof. Avi Wigderson
                  Expander Graphs - where Combinatorics and Algebra
                  Compete and Cooperate

10:55  - 11:05    Short break 

11:05  - 12:00    Dr. Laxmi Parida
                  Pattern Discovery in Computational Biology

12:00  -  2:00    Lunch break

 2:00  -  2:55    Prof. Sanjeev Khanna
                  Algorithms for Minimizing Weighted Flow Time

 2:55  -  3:15    Coffee break

 3:15  -  4:10    Dr. Peter Winkler
                  Building Uniform Subtrees of a Cayley Tree

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

Organizers:
Yevgeniy Dodis   dodis@cs.nyu.edu
Tal Rabin        talr@watson.ibm.com
Baruch Schieber  sbar@watson.ibm.com

=======================================================================
                              Abstracts

            Expander graphs - where Combinatorics and Algebra 
                         Compete and Cooperate 

                          Prof. Avi Wigderson 
               (IAS Princeton and The Hebrew University)


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.


                Pattern Discovery in Computational Biology

                      Dr. Laxmi Parida (IBM Research)

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.


               Algorithms for Minimizing Weighted Flow Time

                    Prof. Sanjeev Khanna (CIS, UPenn)


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.

 
               Building Uniform Subtrees of a Cayley Tree
 
                     Dr. Peter Winkler  (Bell Labs)
 
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.