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

- 13 Oct 2000 :
**Mikkel Thorup**(AT&T Labs) . Approximate Distance Oracles. - 9th Nov 2000 :
**Michael Mitzenmacher**(Harvard University) . Using Multiple Hash Functions to Improve IP Routing. - 16th Nov 2000 :
**Alistair Sinclair**(UC Berkeley) . Approximating the permanent. - 15th March 2001 :
**David Williamson**(IBM Almaden) . An application of complex semidefinite programming to approximation algorithms. - 19th April 2001 :
**D. Sivakumar**(IBM Almaden) . A sieve algorithm for the shortest lattice vector problem. - 25th April 2001 :
**Tami Tamir**(Technion) . Algorithms for Packing and Scheduling with Constraints. - 17th May 2001 :
**Chandra Chekuri**(Bell Labs) . Algorithms for Minimizing Weighted Flow Time. - 31st May 2001 :
**Ziv Bar-Yossef**(Berkeley). Sampling Algorithms: Lower Bounds and Applications.

This is joint work with Uri Zwick.

The double hashing technique is of general interest for applications othter than IP routing. In particular, in instances where the goal is to have each hash bucket fit into a single cache line, using multiple hashes proves extremely suitable. We provide a general analysis of this hashing technique as well as demonstrate its performance for binary search on levels.

Includes joint work with Berthold Voecking and Andrei Broder.

Joint work with Mark Jerrum and Eric Vigoda.

In particular, we consider the problem of maximizing the total weight of satisfied equations x_u - x_v \equiv c (mod 3) and inequations x_u - x_v \not\equiv c (mod 3), where x_u \in {0,1,2} for all u. This problem can be used to model the MAX 3-CUT problem and a directed variant we call MAX 3-DICUT. For the general problem, we obtain a .79373-approximation algorithm. If the instance contains only inequations (as it does for MAX 3-CUT), we obtain a performance guarantee of 7/12 + (3/(4\pi^2)) arccos^2(-1/4), which is about .83601. This compares with proven performance guarantees of .800217 for MAX 3-CUT (by Frieze and Jerrum) and 1/3 + 10^{-8} for the general problem (by Andersson, Engebretson, and Hastad). A .83601-approximation algorithm for MAX 3-CUT has also been discovered independently by de Klerk, Paschenik, and Warners.

This is joint work with Michel X. Goemans of MIT.

Our SVP algorithm runs in time exp(c n), where n is the dimension of the lattice, and c is a constant. The previous best time upper bound for this problem is from a deterministic algorithm due to Ravi Kannan (1983); his algorithm runs in time exp(d n log n) for some constant d. We will mention some consequences of our algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem.

The exposition will be fairly self-contained. This is joint work with Miklos Ajtai and Ravi Kumar.

A similar constraint can be presented in scheduling problems, where a set of $n$ jobs needs to be scheduled on $m$ uniform machines. Each job, $j$, has a length and an allotment parameter, $a_j$, which specifies the maximal number of machines that can share its execution. The cases where $a_j=1$ (non-preemptive scheduling), and $a_j=m$ (preemptive scheduling), are well-studied. We consider the problem of minimizing the completion time of all jobs (the Makespan) when each job has an arbitrary allotment parameter $1 < a_j < m$.

We present hardness results, approximation algorithms, and characterize classes of instances for which exact solutions can be found efficiently. For example, the scheduling problem is shown to be strongly NP-hard when all the jobs have $a_j = 3$, but solvable optimally when for all the jobs $a_j \ge 5$ (the case where $\forall j, a_j=4$ is open). For the CCMK and the CCBP problems we present polynomial time approximation schemes. Optimal algorithms are presented for the CCMK and FPP problems with identical knapsacks and unit-sized items.

The talk is based on my Ph.D thesis. Thesis advisor: Dr. Hadas Shachnai.

We discuss some new on-line and off-line algorithms for the weighted problem on a single machine. We show a semi-online algorithm for the single machine problem that has an O(\log^2 P) competitive ratio. Here P is the ratio of the maximum job size to the minimum job size. In the off-line setting we show that a (2+\eps)-approximation is achievable in quasi-polynomial time. We show an \Omega(\sqrt{P}) lower bound on online algorithms for multiple machines, this is in contrast to the un-weighted flow time for which SRPT achieves a logarithmic competitive ratio. We also discuss improved ratios for minimizing total stretch on multiple machines, an interesting special case of weighted flow time, where the weight of a job is inversely proportional to its processing time.

Time permitting, we will discuss some recent work that yields approximation schemes for weighted flow time.

Joint work with Sanjeev Khanna and An Zhu.

We define two quantitative properties of functions - the block sensitivity and the minimum Hellinger distance - that give us techniques to prove lower bounds on the query complexity. These techniques are quite general, easy to use, yet powerful enough to yield tight results. Our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds.

Joint work with Ravi Kumar and D. Sivakumar.