enter search term and/or author name
Nonclairvoyant scheduling to minimize the total flow time on single and parallel machines
Luca Becchetti, Stefano Leonardi
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
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
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
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
We present a general technique for approximating various descriptors of the extent of a set P of n points in Rd 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
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
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...