SAS is the Stanford Algorithms Seminar (formerly the AFLB -- Algorithms for Lunch Bunch). It is run by Suresh Venkatasubramanian. Meetings are generally Thursdays at 4:15 p.m.

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

Contents:

  1. 9 October 1997: Bernhard von Stengel (ETH Zurich). New Maximal Numbers of Equilibria in Bimatrix Games.
  2. 16 October 1997: Steven Rudich (Carnegie Mellon). Reducing the Complexity of Reductions.
  3. 20 November 1997: Michael Mitzenmacher (Digital SRC). How Useful is Old Information?
  4. 4 December 1997: Ashish Goel (Stanford). Online Multicast Routing and Admission Control.
  5. 16 January 1998: Eli Gafni (UCLA). Geometric Protocols.
  6. 22 January 1998: David Karger (MIT). Better random sampling algorithms for cuts and flows in undirected graphs.
  7. 29 January 1998: Vincenzo Liberatore (Rutgers). Broadcast Disk Paging.
  8. 5 February 1998: Chandra Chekuri (Stanford). Approximating a finite metric by O(n \log n) trees with applications to approximation algorithms.
  9. 12 February 1998: Amnon Ta-Shma (ICSI). How much information can k qbits contain?.
  10. 19 February: Irit Dinur (Tel Aviv University). Approximating-CVP to within almost polynomial factors is NP-hard.
  11. 26 February: Andrew Goldberg (NEC). Towards an Archival Intermemory.
  12. 5 March 1998: Piotr Indyk (Stanford University). Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality .
  13. 27 Apr 1998: Vijay Vazirani (Georgia Tech). The Steiner Tree Problem and its Generalizations.
  14. 30 Apr 1998: Igor Shparlinski (Macquarie University). Polynomial Approximation of the Discrete Logarithm and Related Problems.
  15. 7 May 1998: Moni Naor (Weizmann Institute). A Formal Treatment of Remotely Keyed Encryption.
  16. 21 May 1998: Uriel Feige (Weizmann Institute). Approximating the bandwidth via volume respecting embeddings.

9 October 1997

Gates Building 498. 4:15 p.m.

Bernhard von Stengel (ETH Zurich)

New Maximal Numbers of Equilibria in Bimatrix Games

The Nash equilibrium is the central solution concept for noncooperative games. In general, such an equilibrium requires randomized strategies of the players, and it is not unique. As a tool for game-theoretic analysis, algorithms for finding Nash equilibria have found increasing interest. When looking for all equilibria of the game, what are worst-case upper and lower bounds for the output size of the algorithm? For two-person (bimatrix) games, we show the first nontrivial lower bound using polytope theory.

Quint and Shubik conjectured in 1994 that nondegenerate n x n bimatrix games have at most 2^n-1 equilibria, which is the case for the simple ``coordination game'' where each player's payoffs are given by the identity matrix. We present a class of counterexamples to this conjecture for n=6 (with a game that has 75 equilibria) and all n>7, with asymptotically more than 2.414^n equilibria. Compared with the earlier lower bound of 2^n, this is not far from the upper bound of about 2.6^n known from the Upper Bound Theorem for polytopes. This suggests that algorithms for determining all equilibria are best implemented using vertex enumeration. Our construction is based on cyclic polytopes with a suitable permutation of their ``facet labels'' that are used to represent the complementarity condition of an equilibrium.

The talk will emphasize the geometric intuition behind the construction. No prior knowledge of the technical concepts is required.

Email: stengel@inf.ethz.ch
WWW: http://www.inf.ethz.ch/personal/stengel
Related paper: ftp://ftp.inf.ethz.ch/pub/publications/tech-reports/2xx/264.ps.gz

16 October 1997

Gates Building 498. 4:15 p.m.

Steven Rudich (Carnegie Mellon)

Reducing the Complexity of Reductions

The theory of NP-completeness is based on the notion of polynomial time reduction between sets, but the same theory can be based on much weaker notions of reduction. For example, all the NP-complete sets listed in Garey and Johnson remain NP-complete under LOGSPACE reductions. In fact, they all remain NP-complete under AC^0 reductions.

One of the outstanding questions in the theory of NP-completeness is the twenty year old Berman-Hartmanis conjecture. The conjecture states that all the sets complete for NP under polynomial time reductions are polynomial time isomorphic. In this talk, we prove the Berman-Hartmanis conjecture for AC^0 reductions: all sets complete for NP under AC^0 reductions are AC^0 isomorphic. Thus, all the thousands of NP-complete sets encountered in the literature are AC^0 (depth 3) isomorphic.

What makes our result possible is a technique to reduce the complexity of any AC^0 reduction between two NP-complete sets to something almost trivial to compute and invert. The new, simpler reduction is a subtle transformation of the original, requiring application of the Hastad Switching Lemma.

We also give a construction for what is (to the best of our knowledge) the first NP-complete set for which there is no AC^0 reduction from Satisfiability.

More formally, we show three theorems that hold for any complexity class C closed under (uniform) TC^0-computable many-one reductions.

  1. ISOMORPHISM: The sets complete for C under AC^0 reductions are all isomorphic under isomorphisms computable and invertible by AC^0 circuits of depth three.

  2. GAP: The sets that are complete for C under AC^0 and NC^0 reducibility coincide.

  3. STOP GAP: The sets that are complete for C under AC^0 + PARITY and AC^0 reducibility do not coincide.

(These theorems hold both in the non-uniform and P-uniform settings.) To prove the second theorem for P-uniform settings, we show how to derandomize a version of the switching lemma, which may be of independent interest.

(This is joint work with M. Agrawal, W. Allender, R. Impagliazzo, and T. Pitassi)

Email: rudich@CS.cmu.EDU
WWW: http://www.cs.cmu.edu/~rudich
Related paper: http://www.cs.cmu.edu/~rudich/papers/reducing_reductions.ps

20 November 1997

Gates Building 498. 4:15 p.m.

Michael Mitzenmacher (Digital SRC)

How Useful is Old Information?

We consider the problem of load balancing in dynamic distributed systems in cases where new incoming tasks can make use of old (stale) load information. For example, consider a multi-processor system where incoming tasks with exponentially distributed service requirements arrive as a Poisson process, the tasks must choose a processor for service, and when making this choice a task knows the processor loads from $T$ seconds ago. What is a good strategy for choosing a processor, in order for tasks to minimize their expected time in the system? Such models can also be used to describe settings where there is a transfer delay between the time a task enters a system and the time it reaches a processor for service.

Our models our based on considering the behavior of limiting systems where the number of processors goes to infinity. The limiting systems can be shown to accurately describe the behavior of sufficiently large systems, and simulations demonstrate that they are reasonably accurate even for systems with a small number of processors. Our studies of specific models demonstrate the importance of using randomness to break symmetry in these systems and yield important rules of thumb for system design. The most significant result is that only small amounts of load information can be extremely useful in these settings; for example, having incoming tasks choose the least loaded of two randomly chosen processors is extremely effective over a large range of possible system parameters. In contrast, using global information can actually degrade performance unless used correctly; for example, unlike most settings where the load information is current, having tasks go to the least loaded server can significantly hurt performance.

Email: michaelm@pa.dec.com
WWW: http://www.research.digital.com/SRC/personal/michaelm/home.html
Related paper: http://www.research.digital.com/SRC/personal/michaelm/WORK/old.ps

4 December

Gates Building 498. 4:15 p.m.

Ashish Goel

Online Multicast Routing and Admission Control

The problem we address is the following: requests for joining existing multicast circuits arrive in an online fashion in a capacitated network. As soon as a request arrives, the online algorithm must either reject it or produce a route that connects the requesting node to the multicast circuit. The twin problems of online routing and admission control have been studied well for unicast circuits. These problems become much more complicated for multicast. We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to the expected number of requests accepted by our algorithm is $O((\log n+ \log\log {\cal M})(\log n+\log {\cal M})\log n)$, where $\cal M$ is the number of multicast groups and $n$ is the number of nodes in the graph. We show that this is close to optimum by presenting an $\Omega(\log n \log \cal{M})$ lower bound on this ratio for any randomized online algorithm against an oblivious adversary, when $\cal{M}$ is much larger than the link capacities. Our lower bound applies even in the restricted case where the link capacities are much larger than bandwidth requested by a single multicast. We also present a simple proof showing that it is impossible to be competitive against an adaptive online adversary.

This is joint work with Monika Henzinger (Digital SRC) and Serge Plotkin (Stanford University).

Email: agoel@cs.stanford.edu
WWW: http://www-cs-students.stanford.edu/~agoel
Related paper: http://www-cs-students.stanford.edu/~agoel/selective-multicast.ps

16 January 1998

Gates Building 498. 4:15 p.m.

Eli Gafni (UCLA)

Geometric Protocols

The Iterated Immediate Snapshots model of distributed computation, recently introduced and proved equivalent to the standard wait-free asynchronous model, lends itself to a natural effective embedding in $R^n$, with runs associated with points, and views associated with neighborhoods. Fixing an embedding one can state a protocol as a geometric condition: When processor $P_i$'s view satisfies geometric condition $X$ then output $Y$. This paper investigates the utility and insight of stating protocols in terms of geometry. It first shows by the way of an example that some problems that yield unwieldy protocols are trivially stated geometrically. Secondly, it takes the first step toward a geometric characterization of which non-terminating tasks yield wait-free, rather than non-blocking protocols. It shows that wait-free is associated with only countable number of exceptions to the requirement to produce outputs, while non-blocking is associated with an uncountable number.

Email: eli@cs.ucla.edu
WWW: http://www.cs.ucla.edu/csd-lanai/fweb/eli.html
Related paper: http://www.cs.ucla.edu/csd-lanai/fweb/eli/podc2col.ps

22 January 1998

Gates Building 498. 4:15 p.m.

David Karger (MIT)

Better random sampling algorithms for cuts and flows in undirected graphs

We present new algorithms, based on random sampling, that find minimum cuts and maximum flows in undirected graphs. Our talk is self contained, but builds upon our previous work which showed that random sampling preserves the values of all cuts in an undirected graph. As a first step, we present improved methods for sampling from capacitated graphs. Large edge capacities can cause large variances in the outcomes of sampling experiments, so we introduce a "smoothing" technique that eliminates these large deviations while keeping our samples small. This smoothing technique yields an algorithm for approximating minimum cuts arbitrarily closely in $O(n^2)$ time and for approximating maximum flows arbitrarily closely in $O(m\sqrt{n})$ time. We also devise exact maximum flow algorithms that draw upon the classical augmenting-path method for finding flows. We use random sampling to find these augmenting paths without examining all the edges. Roughly speaking, given an $m$-edge $n$-vertex graph, our algorithm performs its augmentations in amortized time $O(\sqrt{mn})$ per augmentation. This compares favorably with the $O(m)$ time bound of standard augmenting paths and also dominates blocking flows over a large range of parameter values. Email: karger@lcs.mit.edu
WWW: http://www.toc.lcs.mit.edu/~karger/

29 January 1998

Gates Building 498. 4:15 p.m.

Vincenzo Liberatore (Rutgers)

Broadcast Disk Paging

Broadcast disks are an emerging paradigm for massive information dissemination. In broadcast disks, data is divided into n equal-sized pages and pages are broadcast in a round-robin manner by a server. Broadcast disks are effective because many clients can simultaneously retrieve any transmitted information. Paging is used by the clients to improve performance, much as in virtual memory systems. However, paging on broadcast disks differs from virtual memory paging in many fundamental aspects. In particular, page faults have dynamically changing costs, and prefetching is provably essential for achieving good competitive ratios. In this talk, we present a deterministic algorithm that uses prefetching to achieve an O(n log k) competitive ratio for the broadcast disk paging problem when the client has a cache of size k. We also show a matching lower bound of Omega(n log k) that applies even when the adversary is not allowed to use prefetching. Moreover, we show a lower bound of Omega(n log k) on the competitive ratio achievable by any non-prefetching randomized algorithms against an oblivious adversary. A curious interpretation of our results is that in the broadcast disk paging, prefetching is a perfect substitute for randomization.

(This is joint work with Sanjeev Khanna.)

Email: liberato@bothrops.rutgers.edu
WWW: http://paul.rutgers.edu/~liberato/

5 February 1998

Gates Building 498. 4:15 p.m.

Chandra Chekuri (Stanford)

Approximating a finite metric by O(n \log n) trees with applications to approximation algorithms

Most optimization problems on an undirected graph reduce in complexity when restricted to instances on a tree. A recent result by Bartal for probabilistically approximating graph metrics by trees shows the following. There is a probability distribution on a space of the spanning trees of the graph such that no edge stretches (in an expected sense) by more than a factor of $O(\log n \log\log n)$. This has resulted in approximation algorithms for several problems which exploit the ease of solving problems on trees. The tree construction of Bartal is inherently randomized and a natural question to ask is whether approximation algorithms which use this construction can be derandomized.

We obtain the following result. We show that any finite metric of size $n$ can be probabilistically approximated by $O(n \log n)$ trees such that the distortion of any edge is at most a factor of $O(\log n \log \log n)$. Further the trees and the associated probability distribution can be constructed efficiently in polynomial time. The implications of the result are twofold. First, the construction gives alternate proofs of the constructions of Bartal. Second, the polynomial size of the space we are sampling from enables us to derandomize any approximation algorithm based on above construction. We obtain the first deterministic approximation algorithms for several problems including group Steiner trees, $k$-median, buy-at-bulk network design, minimum communication spanning trees, and vehicle routing. For the group Steiner problem we derandomize the rounding scheme of Garg et al. who give a randomized approximation algorithm for solving the problem on trees.

In this talk I will describe the above construction and time permitting the derandomization scheme for group Steiner problem on trees.

This talk is based on a paper with Moses Charikar, Ashish Goel and Sudipto Guha to appear in STOC 98, and recent improvements with the above and Serge Plotkin.

Email: chekuri@cs.stanford.edu
WWW: http://Theory.Stanford.EDU/~chekuri/

12 February 1998

Gates Building 498. 4:15 p.m.

Amnon Ta-Shma

How much information can k qbits contain?

Kholevo's Theorem states that only k classical bits of information can be obtained from k qbits. Yet, Kholevo's theorem does not rule out the possibility that only one bit of information is obtained, BUT OF OUR CHOICE. More precisely we deal with the following question:

Is it possible to encode an n bit classical input x into k qbits, s.t.

for ANY $v=v(x)$ and

for ANY $1 \le i \le n$

a decoder can recover $x_i$ from $v=v(x)$ with success probability of at least 1/2+epsilon. We call such a scheme an n->k encoding with epsilon advantage.

In other words: Instead of asking how much information can be obtained from k qbits, we ask how much information can be put into k qbits, s.t. each part of it is accessible.

Indeed, a simple example shows that a 2->1 encoding with success probability of 0.86.. exists. We prove that no classical 2->1 encoding with any positive advantage exists, thus showing a fundamental difference between classical and quantum encodings.

In the talk I'll present a proof that even in the quantum world, there is no way to encode n -> n/clog(n) with a constant advantage. One notable variant of the problem which is not covered by our proof, is the variant where we replace the requirement "for any 1 \le i \le n$ with the weaker requirement "for MOST i, 1 \le i \le n". We do not know yet whether this is a technical detail, to be fixed by a better proof, or not.We point out that this might have implications to a new model we define, QNP (for "QUANTUM NP").

This work is joint work with Umesh Vazirani.

Email: amnon@ICSI.Berkeley.EDU
WWW: http://www.icsi.berkeley.edu/~amnon/

19 February

Gates Building 498. 4:15 p.m.

Irit Dinur (Tel Aviv University)

Approximating-CVP to within almost polynomial factors is NP-hard

Given a lattice $L$ and an arbitrary vector $y$, the closest vector problem (CVP) is to find a vector in $L$ that is closest to $y$. The shortest vector problem (SVP) is the homogeneous analog of CVP, i.e. finding the shortest non-zero vector in $L$.

An exciting new result by Ajtai, proved the equivalence of average-case and worst-case complexity of unique-SVP, a variant of these problems. Ajtai-Dwork consequently presented a crypto-system based on unique-SVP and proved that breaking it implies approximating unique-SVP to within some polynomial factor. These results stress the significance of finding the hardness of these lattice problems.

We show (using the PCP characterization of NP [RaSa, DFKRS]) that approximating CVP to within an almost-polynomial factor is NP-hard. The SVP problem has only recently been shown to be NP-hard [Ajtai]. On the other hand Goldreich and Goldwasser showed that approximating CVP and SVP up to a $\sqrt{dim}$ factor is in $co-AM$, and is therefore unlikely to be NP-hard. It was already known [ABSS] that approximating CVP up to an almost-polynomial factor is {\it quasi-NP-hard}, i.e. implies $NP \subset P^{poly-log}$.

Joint work with G. Kindler and S. Safra.

Email: dinur@math.tau.ac.il
WWW:
Related paper:

26 February

Gates Building 498. 4:15 p.m.

Andrew Goldberg (NEC)

Towards an Archival Intermemory

We propose a self-organizing archival Intermemory: a noncommercial subscriber-provided distributed information storage service built on the existing Internet. Given an assumption of continued growth in the memory's total size, a subscriber's participation for only a finite time can nevertheless ensure archival preservation of the subscriber's data. Information disperses through the network over time and memories become more difficult to erase as they age. The probability of losing an old memory given random node failures is vanishingly small -- and an adversary would have to corrupt hundreds of thousands of nodes to destroy a very old memory.

We show that such an Intermemory is possible and present a framework for the design of an Intermemory. We also consider certain aspects of the design in greater detail. In particular, the aspects of addressing, space efficiency, and redundant coding are discussed.

(joint work with Peter N. Yianilos)

Email: avg@research.nj.nec.com
WWW: http://www.neci.nj.nec.com/homepages/avg/
Related paper:

5 March 1998

Gates Building 498. 4:15 p.m.

Piotr Indyk (Stanford University)

Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality

The nearest neighbor problem is the following: Given a set of n points P in some metric space X, preprocess P so as to efficiently answer queries which require finding the point in P closest to a query point q \in X. We focus on the particularly interesting case of the d-dimensional Euclidean space where X = Re^d under some l_p norm. The current solutions are far from satisfactory; in fact, for large enough d, they provide little improvement over the brute-force algorithm which compares the query point to each data point. Of late, there has been some interest in the approximate nearest neighbors problem, which is: Find a point p \in P that is an epsilon-approximate nearest neighbor of the query q in that for all p' \in P, d(p,q) < (1+epsilon) d(p',q).

In this talk I will present two algorithmic results for the approximate version that significantly improve the known bounds:

(a) preprocessing cost polynomial in n and d, and a query time polynomial in log n and d,

(b) preprocessing cost O(dn^{1+1/epsilon}) and a query time O(dn^{1/epsilon}) (for epsilon > 1),

We will also discuss experimental results indicating that the second algorithm offers significant improvement on running times over real data sets. We discuss its applications to information retrieval, pattern recognition, dynamic closest-pairs, and fast clustering algorithms.

This is joint work with Aris Gionis (the experimental part) and Rajeev Motwani.

Email: indyk@cs.stanford.edu
WWW: http://theory.stanford.edu/~indyk/
Related paper:

27 Apr 1998

Gates Building 463. 4:15 p.m.

Vijay Vazirani (Georgia Tech)

The Steiner Tree Problem and its Generalizations

The Steiner tree problem was defined by Gauss in a letter to Schumacher. This problem occupies a central place in the emerging theory of approximation algorithms -- methods devised to attack it have led to fundamental paradigms for the rest of the area. Despite intense work on this problem and its generalizations over the last ten years, there are vast gaps in our understanding. This talk will concentrate on Jain's recent breakthrough result (giving a factor 2 algorithm for the generalized Steiner network problem), and directions worth exploring in the future.

Email: vazirani@cc.gatech.edu
WWW: http://www.cc.gatech.edu/people/home/kjain/
Related paper:

30 Apr 1998

Gates Building 498. 4:15 p.m.

Igor Shparlinski (Macquarie University)

Polynomial Approximation of the Discrete Logarithm and Related Problems

Several exponential (in terms of \log p) lower bounds are obtained on the degrees and orders of

- polynomials;

- algebraic functions;

- Boolean functions;

- linear recurrent sequences;

coinciding with values of the discrete logarithm modulo a prime $p$ at sufficiently many points (the number of points can be as little as $p^{1/2 +\varepsilon}$). These functions are considered over the residue ring modulo $p$ and over the residue ring modulo an arbitrary divisor $d$ of $p-1$. The case of $d=2$ is of special interest since it corresponds to the representation of the rightmost bit of the discrete logarithm and defines whether the argument is a quadratic residue.

These results are used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm.

The method is based on bounds of character sums and numbers of solutions of some polynomial equations.

Similar results are obtained for breaking the Diffie--Hellman cryptosystem.

Email: igor@mpce.mq.edu.au
WWW: http://www.comp.mq.edu.au/~igor
Related paper:

7 May 1998

Gates Building 498. 4:15 p.m.

Moni Naor (Weizmann Institute)

A Formal Treatment of Remotely Keyed Encryption

Remotely keyed encryption schemes (RKESs) support high-bandwidth cryptographic applications in which long-lived secrets (such as users' private keys) never leave the lower-bandwidth environment, for instance a secure smart-card. We provide a formal framework for studying the security of RKESs and suggest RKESs that satisfy our formal security requirements. These schemes are efficient in that the amount of communication and computation that they require of the smart-card is independent of the input size. Our proof of security uses the pseudorandom permutation framework of Naor and Reingold in an essential way.

Joint work with Matt Blaze and Joan Feigenbaum from AT&T Labs

Email: naor@wisdom.weizmann.ac.il
WWW: http://www.wisdom.weizmann.ac.il/~naor/
Related paper: http://www.wisdom.weizmann.ac.il/~naor/PAPERS/smart.ps

21 May 1998

Gates Building 498. 4:15 p.m.

Uriel Feige (Weizmann Institute)

Approximating the bandwidth via volume respecting embeddings

A connected $n$-vertex graph naturally induces a metric on its vertices, where the distance between two vertices is the length of the shortest path connecting them. We introduce a notion of volume for sets of vertices in graphs. We then extend the low distortion embeddings of graphs in Euclidean space (developed by Bourgain and by Linial, London and Rabinovich) to account not only for distances, but also for volumes. The usefulness of our theory of volume respecting embeddings is demonstrated on the problem of computing the bandwidth of a graph - a well known NP-hard problem related to efficient manipulation of large sparse symmetric matrices. We develop a randomized algorithm that runs in slightly superlinear time and approximates the bandwidth within factors of $(\log n)^{O(1)}$. Previously, even an approximation ratio of $n^{1-\epsilon}$ was not known to be achievable for this problem. Our algorithm was implemented and preliminary experimental results are available.

Email: feige@wisdom.weizmann.ac.il
WWW: http://www.wisdom.weizmann.ac.il/~feige/
Related paper: