enter search term and/or author name
Primality and identity testing via Chinese remaindering
Manindra Agrawal, Somenath Biswas
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
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
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
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
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
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
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...