Talks are held in the Gates Building, near the Main Quad of Stanford's campus. Click here for directions.

- 7 Oct 1999:
**Uri Zwick**(Tel Aviv University). All Pairs Shortest Paths in Undirected Graphs. - 9 Dec 1999:
**Marek Karpinski**(University of Bonn). Sorting by Reversals is Hard to Approximate Within Certain Constant. - 6 Jan 2000:
**Matthew Andrews**(Bell Labs). The effects of connection duration on network performance. - 7 Jan 2000 (Friday !):
**Chandra Chekuri**(Bell Labs). A PTAS for the Multiple Knapsack Problem. - 13 Jan 2000 :
**Eran Halperin**(Tel Aviv Univ.). Approximation algorithms for the vertex cover problem in graphs and hypergraphs. - 20 Jan 2000 :
**Martin Strauss**(AT&T Research). Testing and Spot-Checking of Data Streams. - 3 Feb 2000 :
**Andrew Goldberg**(Intertrust STAR Labs). Gomory-Hu Algorithms: an Experimental Study. - 17 Feb 2000 :
**Ron Fagin**(IBM Almaden). Random Walks with "Back Buttons". - 24 Feb 2000 :
**Andris Ambainis**(UC Berkeley). Quantum lower bounds by quantum arguments. - 2 Mar 2000 :
**Sridhar Rajagopalan**(IBM Almaden). The web graph: structure and interpretation. - 9 Mar 2000 :
**Anupam Gupta**(UC Berkeley). Constant Factor Approximation Algorithms for a Class of Classification Problems - 6 Apr 2000 :
**S. Cenk Sahinalp**(Case Western). Approximate Sequence Nearest Neighbours with Block Operations. - 13 Apr 2000 :
**Cynthia Dwork**(IBM Almaden). Zaps and Apps. - 20 Apr 2000 :
**T. C. Hu**(UC San Diego). Local Indexing Algorithms. - 4 May 2000 :
**Mark Huber**(Dept of Statistics, Stanford). A new approach to perfect sampling from nasty distributions. - 11 May 2000 :
**Alon Rosen**(Weizmann). On the round-complexity of concurrent zero-knowledge. - 18 May 2000 :
**Robert Krauthgamer**(Weizmann) . Approximation algorithms for minimum bisection. - 25 May 2000 :
**Sampath Kannnan**(AT&T and Univ of Pennsylvania) . New Instability Results for Contention Resolution Protocols. - 8 June 2000 :
**Dharmendra S. Modha**(IBM Almaden) . Clustering Hypertext with Applications to Web Searching.

Joint work with Avi Shoshan

(Joint work with P.Berman.)

This work is joint with Lisa Zhang and will be presented at SODA '00.

Joint work with Sanjeev Khanna.

This talk presents joint work with Joan Feigenbaum, Sampath Kannan, and Mahesh Viswanathan. It will appear at the SODA'00 conference. A full paper is available.

This is joint work with Kostas Tsioutsiouliklis (Princeton University)

This talk represents joint research with Anna Karlin, Jon Kleinberg, Prabhakar Raghavan, Sridhar Rajagopalan, Ronitt Rubinfeld, Madhu Sudan, and Andrew Tomkins. The talk will be self-contained.

Collaborators: Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Raymie Stata, Andrew Tomkins, Eli Upfal and Janet Wiener.

We consider an important case of the metric labeling problem, in which the metric is the truncated linear metric. This is a natural non-uniform and robust metric which arises in a number of applications, especially in vision. We give a combinatorial 4-approximation algorithm for this metric. Our algorithm is a natural local search algorithm, where the local steps are based on minimum cut computations in an appropriately constructed graph. Our method extends previous work by Boykov, Veksler and Zabih on more restricted classes of metrics.

Joint work with Eva Tardos.

Joint work with S. Muthukrishnan.

Joint work with M. Naor.

Joint work with Leslie Goldberg, Mike Paterson (Univ. of Warwick) and Mark Jerrum (Univ. of Edinburgh)

This is joint work with W. Scott Spangler and will appear in the ACM Hypertext 2000 Conference.