PhD MIT, 1996
My research interests are centered around discrete algorithms and
some of their applications.
One major focus of my work is in combinatorial optimization and
approximation algorithms for NP-hard problems. E. Tardos, Y. Rabani, and I have been
looking at approximation algorithms for routing problems in networks subject to capacity
constraints; some of our recent work has considered cases in which the bandwidth
requirements of connections are bursty, and modeled in a probabilistic framework. I am
also interested in the study of network traffic as a dynamic phenomenon; A. Borodin, P.
|M. Sudan, D. Williamson and I developed
and analyzed an "adversarial" model for the evolution of traffic in a network,
which allows one to study the stability properties of packet-routing networks without
I also work on discrete algorithms for indexing and
clustering high-dimensional data. I developed methods for performing efficient
nearest-neighbor search in high-dimensional Euclidean spaces by "synthesizing"
the results of a large number of randomly chosen low-dimensional projections. I have
developed techniquesbased on spectral graph analysisto use the link structure
of a hypermedia environment such as the World Wide Web in order to identify
"authoritative" information resources. The continued development of these
techniques into a general methodology for hyperlink-oriented search tasks is being pursued
with S. Chakrabarti, B. Dom, D. Gibson, P. Raghavan, and S. Rajagopalan. And, with C.
Papadimitriou and P. Raghavan, I have been studying a model of "segmented
optimization problems", which are designed to address some of the optimization issues
inherent in certain clustering and data-mining operations.
I am also interested in geometric and combinatorial
techniques for algorithmic problems in molecular biology. I am adapting techniques from
discrete optimization to models of polymer sequence design proposed in the biochemistry
community. In addition to providing efficient algorithms, these techniques offer a novel
computational perspective from which to study the structure of certain "evolutionary
networks" on polymer sequences. The definition of a robust and efficiently computable
notion of "geometric similarity" on three-dimensional conformations is also a
problem of considerable interest; I work in this area with P. Chew, D. Huttenlocher, and
Computer Science Faculty Recruiting Committee,
Fields of Computer Science, Applied Math, and Operations Research
Program Committee: IEEE Symp. Foundations of
Computer Science, 1998; Int. Workshop on the Web and Databases, 1998
Authoritative sources in a hyperlinked
environment. Computer Science, MIT, April 1998.
___. Computer Science, Brown Univ., April 1998.
___. ACM-SIAM Symp. Discrete Algorithms, Jan.
___. Computer Science, Univ. Toronto, Nov. 1997.
Analysis of hypermedia. NSF-IMA Workshop on
Knowledge and Distributed Intelligence, March 1998.
Decision algorithms for unsplittable flow. ACM.
Theory of Computing, May 1998.
Decision algorithms for unsplittable flow and the
half-disjoint paths problem. Proc. 30th ACM Symp. Theory Computing (1998), 530-539.
Segmentation problems. Proc. 30th ACM Symp.
Theory of Computing(1998). (with C. Papadimitriou and P. Raghavan).
Automatic resource compilation by analyzing
hyperlink structure and associated text. Proc. 7th Int. World Wide Web Conf.
(1998), 65-74 (with S. Chakrabarti, B. Dom, D. Gibson, P. Raghavan, and S. Rajagopalan).
Authoritative sources in a hyperlinked
environment. Proc. 9th ACM-SIAM Symp. (1998), 668-677.
The Lovasz theta function and a semi-definite
programming relaxation of vertex cover. SIAM J. Discrete Math. 11 (1998), 196-204
(with M. Goemans).
Storage management for evolving databases. Proc.
38th IEEE Symp. Found. Computer Science (1997), 353-362 (with R. Motwani, P. Raghavan,
and S. Venkatasubramanian).