My research is centered around the design of efficient algorithms, with an emphasis on combinatorial optimization, discrete algorithms for networks, and problems in high-dimensional geometry. Many basic problems in these domains are computationally intractable, and I am interested in developing approximation algorithms with provable performance guarantees for such problems.

 A major focus of my work has been on the algorithmic problems that arise large-scale communication networks. Such networks, and their technological precursors, are closely connected with many of the core issues of combinatorial optimization, such as multicommodity flow and disjoint paths in graphs. In recent work with Eva Tardos, we developed approximation algorithms for versions of the disjoint paths problem arising in the context of virtual circuit routing. I also recently developed approximation algorithms for a related NP-hard routing problem, "unsplittable flow", for terminals connected to a single source in an arbitrary network.

 In a related vein, I have been investigating new models in which to study the stability of packet-routing networks that must operate continuously over time. With Allan Borodin, Prabhakar Raghavan, Madhu Sudan, and David Williamson, we developed and analyzed an "adversarial" model for packet generation in a network, which allows one to prove stability properties without probabilistic assumptions.

 I am interested in using techniques from high-dimensional geometry to attack a wide array of hard algorithmic problems. I have been applying such techniques in domains ranging from the approximation of discrete optimization problems to the efficient indexing of numerical data. One line of work concerns the interplay between these methods and some notoriously intractable problems in low-dimensional geometry, such as biomolecular structure prediction and general geometric embedding problems.

 Awards

Professional Activities

 Lectures

Publications