Search ACM DL

Search Issue

enter search term and/or author name

**Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines**

Luca Becchetti, Stefano Leonardi

Pages: 517-539

DOI: 10.1145/1008731.1008732

Scheduling a sequence of jobs released over time when the processing time of a job is only known at its completion is a classical problem in CPU scheduling in time sharing operating systems. A widely used measure for the responsiveness of the system...

**Solving convex programs by random walks**

Dimitris Bertsimas, Santosh Vempala

Pages: 540-556

DOI: 10.1145/1008731.1008733

Minimizing a convex function over a convex set in *n*-dimensional space is a basic, general problem with many interesting special cases. Here, we present a simple new algorithm for convex optimization based on sampling by a random walk. It...

**The random oracle methodology, revisited**

Ran Canetti, Oded Goldreich, Shai Halevi

Pages: 557-594

DOI: 10.1145/1008731.1008734

We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called "cryptographic hash functions".The main...

**Quantum lower bounds for the collision and the element distinctness problems**

Scott Aaronson, Yaoyun Shi

Pages: 595-605

DOI: 10.1145/1008731.1008735

Given a function *f* as an oracle, the collision problem is to find two distinct indexes *i* and *j* such that *f*(*i*) = *f*(*j*), under the promise that such indexes exist. Since the security of many fundamental...

**Approximating extent measures of points**

Pankaj K. Agarwal, Sariel Har-Peled, Kasturi R. Varadarajan

Pages: 606-635

DOI: 10.1145/1008731.1008736

We present a general technique for approximating various descriptors of the extent of a set *P* of *n* points in R^{d} when the dimension *d* is an arbitrary fixed constant. For a given extent measure μ and a...

**Edge-disjoint routing in plane switch graphs in linear time**

Jan M. Hochstein, Karsten Weihe

Pages: 636-670

DOI: 10.1145/1008731.1008737

By a *switch graph*, we mean an undirected graph *G* = (*P* ⊍ *W*, *E*) such that all vertices in *P* (the *plugs*) have degree one and all vertices in *W* (the *switches*) have even degrees. We...

**A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries**

Mark Jerrum, Alistair Sinclair, Eric Vigoda

Pages: 671-697

DOI: 10.1145/1008731.1008738

We present a polynomial-time randomized algorithm for estimating the permanent of an arbitrary *n* × *n* matrix with nonnegative entries. This algorithm---technically a "fully-polynomial randomized approximation scheme"---computes an...