Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 50 Issue 4, July 2003

Editorial: Preserving excellence through change
Prabhakar Raghavan
Pages: 427-428
DOI: 10.1145/792538.792539

Primality and identity testing via Chinese remaindering
Manindra Agrawal, Somenath Biswas
Pages: 429-443
DOI: 10.1145/792538.792540
We give a simple and new randomized primality testing algorithm by reducing primality testing for number n to testing if a specific univariate identity over Zn holds.We also give new randomized algorithms for testing if a...

Algorithms adapting to point contention
Hagit Attiya, Arie Fouren
Pages: 444-468
DOI: 10.1145/792538.792541
This article introduces the sieve, a novel building block that allows to adapt to the number of simultaneously active processes (the point contention) during the execution of an operation. We present an implementation of the sieve in...

Computability theory of generalized functions
Ning Zhong, Klaus Weihrauch
Pages: 469-505
DOI: 10.1145/792538.792542
The theory of generalized functions is the foundation of the modern theory of partial differential equations (PDE). As computers are playing an ever-larger role in solving PDEs, it is important to know those operations involving generalized functions...

Noise-tolerant learning, the parity problem, and the statistical query model
Avrim Blum, Adam Kalai, Hal Wasserman
Pages: 506-519
DOI: 10.1145/792538.792543
We describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. Our algorithm runs in polynomial time for the...

Bounds on delays and queue lengths in input-queued cell switches
Emilio Leonardi, Marco Mellia, Fabio Neri, Marco Ajmone Marsan
Pages: 520-550
DOI: 10.1145/792538.792544
In this article, we develop a general methodology, mainly based upon Lyapunov functions, to derive bounds on average delays, and on averages and variances of queue lengths in complex systems of queues. We apply this methodology to cell-based switches...

Minimizing flow time nonclairvoyantly
Bala Kalyanasundaram, Kirk R. Pruhs
Pages: 551-567
DOI: 10.1145/792538.792545
We consider the problem of scheduling a collection of dynamically arriving jobs with unknown execution times so as to minimize the average flow time. This is the classic CPU scheduling problem faced by time-sharing operating systems where preemption...

How asymmetry helps load balancing
Berthold Vöcking
Pages: 568-589
DOI: 10.1145/792538.792546
This article deals with randomized allocation processes placing sequentially n balls into n bins. We consider multiple-choice algorithms that choose d locations (bins) for each ball at random, inspect the content of these...