article

Free Access

On randomization in sequential and distributed algorithms

Authors:
Rajiv Gupta

GE Corporate R & D, K1-5C39, Schenectady, NY

GE Corporate R & D, K1-5C39, Schenectady, NY
View Profile

,
Scott A. Smolka

Department of Computer Science, SUNY at Stony Brook, Stony Brook, NY

Department of Computer Science, SUNY at Stony Brook, Stony Brook, NY
View Profile

,
Shaji Bhaskar

Bell Northern Research, 35 Davis Drive, Research Triangle Park, NC

Bell Northern Research, 35 Davis Drive, Research Triangle Park, NC
View Profile

Authors Info & Claims

ACM Computing Surveys Volume 26 Issue 1pp 7–86https://doi.org/10.1145/174666.174667

Published:01 March 1994Publication History

ACM Computing Surveys

Abstract

Probabilistic, or randomized, algorithms are fast becoming as commonplace as conventional deterministic algorithms. This survey presents five techniques that have been widely used in the design of randomized algorithms. These techniques are illustrated using 12 randomized algorithms—both sequential and distributed— that span a wide range of applications, including:primality testing (a classical problem in number theory), interactive probabilistic proof systems (a new method of program testing), dining philosophers (a classical problem in distributed computing), and Byzantine agreement (reaching agreement in the presence of malicious processors). Included with each algorithm is a discussion of its correctness and its computational complexity. Several related topics of interest are also addressed, including the theory of probabilistic automata, probabilistic analysis of conventional algorithms, deterministic amplification, and derandomization of randomized algorithms. Finally, a comprehensive annotated bibliography is given.

References

ABRAHAMSON, K., ADLER, A., GILBART, R., HIGHAM, L., AND KIRKPATRICK, D. 1989. The bit complexity of randomized leader election on a ring. SIAM J. Comput. 18, 1 (Feb.), 12-29. Under various assumptions about global knowledge, the bit complexity of leader election on asynchronous unidirectional rings is studied. Google ScholarDigital Library
ADLEMAN, L. M. AND HUANG, M.A. 1988. Recognizing primes in random polynomial time. Tech. Rep., Univ. of Southern California, Los Angeles. The authors present a Las Vegas algorithm that looks for witnesses to compositeness as well as those for primality.Google Scholar
ADLEMAN, L. M. AND HUANG, M.A. 1987. Recognizing primes in polynomial time. In Proceedings of the 19th Annual ACM Symposium on Theory of Computmg. ACM, New York, 462-471. The probabilistic algorithms of Rabin {1976} and Solovay and Stassen {1977} placed the problem of compositeness testing in the randomized complexity class RP, and thus the problem of primality testing in co-RP. Adleman and Huang show that primality testing is also in RP, thereby putting this problem in the intersection of RP and co-RP. Google ScholarDigital Library
AGARWAL, P. K. 1990a. Partitioning arrangements of lines I: An efficient deterministic algorithm. Discr. Comput. Geom. 5, 5, 449 483. Using derandomization techniques due to Chazelle and Friedman {1990}, Agarwal obtains a deterministic algorithm that, given a set :~ of n lines and a parameter 1 ~ r ~ n, partitions the plane into O(r2) triangles, each of which meets at most O(n/r) lines of ~'. He shows that the algorithm is optimal up to a polylog factor.Google ScholarDigital Library
AGARWAL, P. K. 1990b. Partitioning arrangements of lines II: Applications. Discr. Comput. Geom. 5, 533-574. Agarwal uses his partitioning algorithm of Agarwal {1990a}, which he derived through derandomization, to obtain efficient algorithms for a variety of problems involving line or line segments in the plane (e.g., computing incidence between points and lines, implicit point location, and spanning trees with low stabbing number). These algorithms are deterministic, faster than previously known algorithms, and optimal up to a polylog factor in many cases.Google ScholarDigital Library
AGGARWAL, A., ANDERSON, R. J., AND KAO, M.-Y. 1990. Parallel depth-first search in general directed graphs. SIAM J. Comput. 19, 2, 397- 409. This paper gives the first randomized NC algorithm for depth-first search in a general directed graph. Google ScholarDigital Library
AIELLO, W. AND HASTAD, J. 1991. Perfect zeroknowledge languages can be recognized in two rounds. J. Comput. Syst. Sci. 42, 3, 327 345. This paper shows that if L has a perfect zeroknowledge proof (see Fikrer et al. {1989} for a definition), then L has a two-round interactive proof if the verifier (of this new IP proof) is permitted a small probability of error in accepting a string w as being in a language L. An earlier version of this paper appeared in Proceedmgs of the 28th Annual IEEE Symposzum on the Foundations of Computer Sczence Google ScholarDigital Library
AJTAI, M. AND WIGDERSON, h. 1989. Deterministic solution of probabilistic constant depth circuits. In Advances zn Computing Research 5: Randomness and Computation. JAI Press, Greenwich, Conn. A family of pseudorandom number generators which appear random to any polynomial-size logic circuit of constant depth and unbounded fan-in is demonstrated. Such pseudorandom generators can be substituted for random number generators in aplclications such as building simple approximations to complex boolean functions {Valiant 1984a}.Google Scholar
AJTAI, M., KOML6S, J., AND SZEMER~DI, E. 1987. Determmmtic simulation in LOGSPACE. In Proceedings of the 19th Annual ACM Sympostum on the Theory of Computing. ACM, New York, 132 140. The authors present an explicit construction of multlgraphs based on expanders for deterministic amplification. Using these multigraphs, Cohen and Wigderson {1989} show that the error probability of any RP or BPP algorithm can be made exponentially small in the size of the input, with only a constant-factor increase in the number of random bits used by the algorithm. Google ScholarDigital Library
ALELUINAS, R. 1982. Randomized parallel communication (preliminary version). In Proceedings of the 1st Annual ACM Symposium. on the Principles of Distributed Computing. ACM, New York, 60-72. This paper presents a randmmzed algorithm for packet delivery that delivers a set of n packets traveling to unique targets from unique sources in O(log n) expected time on a finite-degree interconnection network of n processors. Google ScholarDigital Library
ALLENDER, E.W. 1987. Some consequences of the existence of pseudorandom generators. In Proceedings of the 19th Annual ACM Symposium on the Theory of Computing. ACM, New York, 151 159. Connections between pseudorandom generation, Kolmogorov complexity, and immunity properties of complexity classes are described. Google ScholarDigital Library
ALON, N. AND AZAR, Y. 1988. The average complexity of deterministic and randomized parallel comparison-sorting algorithms. SIAM J. Comput. 17, 6, 1178-1192. Even the averagecase behavior of randomized parallel comparison-sorting algorithms is shown to be no better than the worst-case behavior of their deterministic counterparts. Google ScholarDigital Library
ALON, N. AND NAOR, M. 1993. Coin-flipping games immune against linear-sized coalitions. SIAM J. Comput. 22, 2, 403 417. The authors consider the problem of distributed coinflipping and leader-election algorithms where every process has complete information. They show that for every constant c ~ i there are protocols involving n processes in which no group of cn processes can influence the outcome with probability greater than Kc, where K is a universal constant. Google ScholarDigital Library
ALON, N., BABAI, L., AND ITAL A. 1986. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Alg. 7, 4, 567 583. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximal independent set is an independent set that is not properly contained in any other independent set. The authors present a simple randomized (Las Vegas) parallel algorithm for this problem. On an EREW-PRAM, their algorithm uses {El processors with expected running time O(log~ n), for a graph with n nodes and {E{ edges. Motivated by Karp and Wigderson {1985}, they also describe a derandomization technique to convert any Monte Carlo parallel algorithm that uses k-wise independent random choices into a deterministic parallel algorithm without loss of time and a polynomial increase in the number of processors for any constant k. Google ScholarDigital Library
ALON, N., ERD(~S, P., AND SPENCER, J. $. 1992. The Probabilistic Method. John Wiley and Sons, New York. This paper describes the Probabilistic Method as developed by Paul ErdSs and its applications in discrete mathematics and theoretical computer science.Google Scholar
ALON, N., GOLDREICH, O., HJ4STAD, J., AND PERALTA, R. 1990. Simple construction of almost k-wise independent random variables. In Proceeding8 of the 31st Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 544 553. Three simple constructions of small probability spaces on n bits for which any k bits are almost independent are presented in this paper.Google Scholar
ANGLUIN, D. 1980. Local and global properties in networks of processors. In Proceedings of the 12th Annual ACM Symposium on the Theory of Computing. ACM, New York, 82-93. The capabilities of networks containing nodes w~th nonunique names are analyzed. It ~s shown that there exist networks in which it is not possible to elect a leader (for example, in a ring with four nodes). Other computations, such as determining topology, are also considered. Google ScholarDigital Library
ANGLUm, D. AND VALIANT, L.G. 1979. Fast probabilistic algorithms for Hamiltonian circuits and matching. J. Comput. Syst. Sci. 18, 2, 82-93. The authors present two algorithms with O(n(log n)2) running time for Hamiltonian circuits and an O(n log n) algorithm to find perfect matchings in random graphs with at least cn log n edges, where c is any positive constant.Google Scholar
ARAGON, C. AND SEIDEL, R. 1989. Randomized search trees. In Proceedings of the 30th Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 540-545. A simple randomized algorithm for maintaining balance in dynamic search trees is presented. The expected time for an update is O(log n) on a tree with n nodes and involves fewer than two rotations to rebalance the tree.Google ScholarDigital Library
ARYA, S. AND MOUNT, D. M. 1993. Approximate nearest neighbor queries in fixed dimensions. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 271-280. A randomized algorithm for approximate nearest-neighbor searching is given. Consider a set S of n points in ddimensional Euclidean space, where d is a constant independent of n. The authors produce a data structure, such that given any query point, a point of S will be reported whose distance from the query point is at most a factor of (1 + e) from that of the true nearest neighbor. Their algorithm runs in O(log3 n) expected time and requires O(n log n) space. The data structure can be built in O(n2) expected time. The constant factors depend on d and e. Google ScholarDigital Library
ASPNES, J. AND HERLIHY, M. 1990. Fast randomized consensus using shared memory. J. Alg. 11, 3. An expected O(n4) operations are needed for the solution presented. Google ScholarDigital Library
ASPNES, J. AND WAARTS, O. 1992. Randomized consensus in O(n log2 n) operations per processor. In Proceedings of the 33rd Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 137-146. An asynchronous algorithm is presented that achieves randomized consensus using O(n log2 n) read and write operations on shared-memory registers. This improves on the O(n2 log n) worstcase complexity of the best previously known algorithm.Google Scholar
BABA~, L. 1991. Local expansion of vertextransitive graphs and random generation in finite groups. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing. ACM, New York, 164 174. Babai presents a Monte Carlo algorithm that constructs an efficient nearly uniform random generator for finite groups in a very general setting. Google ScholarDigital Library
BABAI, L. 1985. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on the Theory of Computing. ACM, New York, 421-429. This paper develops interactive proofs to classify certain group-theoretic problems and introduces an alternative notion of interactive proofs for complexity-theoretic analysis. Google ScholarDigital Library
BABAI, L. AND ITA~, A. 1986. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Alg. 7, 4 (Dec.), 567 583. An independent set of a graph is a set of vertices, no two of which are adjacent. A maximal independent set is an independent set that is not a proper subset of any other independent set. A simple algorithm which is always correct and runs in O(log n) time using O(Ed .. ) processors on a Concurrent Read Concurrent Write parallel machine is shown. Here, d~ax is the maximum degree of any vertex in the graph. The earlier best was a deterministic algorithm for an Exclusive Read Exclusive Write architecture that ran in O((log n)4) time using O((n/log n)3) processors. Google ScholarDigital Library
BABAr, L. AND MORAN, S. 1988. Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36, 2, 254-276. The proof system is considered a game played between two players, the verifier and the prover, called Arthur and Merlin, respectively. Arthur and Merlin can toss coins and can talk back and forth. In this type of proof system, all coin tosses made by the verifier are seen by the prover. A hierarchy of complexity classes "just above NP' is derived. Google ScholarDigital Library
BABAI, L., FORTNOW, L., AND LUND, C. 1990. Nondeterministic exponential time has two-prover interactive protocols. In Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 16-25. Babai et al. prove, using the two-prover interactive proof systems introduced in Ben-Or et al.{ 1988a}, that the class of languages that have a two-prover interactive proof system is nondeterministic exponential time.Google ScholarDigital Library
BABAL L., N~SAN, N., AND SZEGEDY, M. 1989. Multiparty protocols and logspace-hard pseudorandom sequences. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. ACM, New York, 1-11. A lower bound is obtained for the bit complexity of computing functions of n variables, where the ith variable resides on processor i. The communication mechanism considered is a shared blackboard. Using this bound, algorithms are developed that generate, in polynomial time, pseudorandom sequences of length n from a seed of length exp(c lol/ogn ). These pseudorandom sequences cannot be distinguished from truly random sequences by any logspace Turing machine. Google ScholarDigital Library
BACH, E. 1991. Realistic analysis of some randomized algorithms. J. Comput. Syst. Sci. 42, 1, 30-53. Bach's analysis justifies the use of pseudorandom substitutes for true random number generators in a random primality tester and a probabilistic algorithm for computing square roots. Google ScholarDigital Library
BAC~, E., MmLER, G., AND SHALLIT, J. 1986. Sums of divisors, perfect numbers and factoring. SIAM J. Comput. 15, 4 (Nov.), 1143-1154. The authors show that computing the sum of divisors of a number N is as hard as factoring N. They also give three natural sets which are in BPP (see Gill {1977}) but are not known to be in RP. Google ScholarDigital Library
BARTAL, Y., FIAT, A., KARLOFF, $., AND VOHRA, R. 1992. New algorithms for an ancient scheduling problem. In Proceedmgs of the 24th Ann ual ACM Symposium on the Theory of Computing. ACM, New York, 51 58. They consider the on-line version of the original m-machine scheduling problem: given m machines and n positive real jobs, schedule the n jobs on m machines so as to minimize the makespan, the completion time of the last job. In the on-line version, as soon as job j arrives, it must be assigned immediately to one of the machines. They present a competitive deterministic algorithm for all m and an optimal randomized algorithm for the case m = 2. Google ScholarDigital Library
BEANIE, r. AND LAWRY, J. 1992 Randomized vs. nondeterministic communication complexity In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 188-199. The authors show that the two complexities are not always the same. Google ScholarDigital Library
BEAUCHEMIN, P., BRASSARD, G., CRI~PEAU, C., GOUTIER, C., AND POMERiNCE, C. 1988. The generation of random numbers that are probably prime. J. CryptoI. 1, 1, 53 64. The authors make two intriguing observations on Rabin's{1976} probabilistic primality test, the subject of Section 2.2 of this survey. The first is a provocative reason why Rabin's test is so good. It turns out that a single iteration of his algorithm has a nonnegligible probability of failing only on composite numbers that can actually be split in expected polynomial time. Therefore, factoring would be easy if Rabin's test systematically failed with a 25% probability on each composite integer (which, of course, it does not). The authors also investigate the question of how reliable Rabin's test is when used to generate a random integer that is probably prime, rather than to test a specific integer for primality. Google ScholarDigital Library
BEmEL, R., REINGOLD, N., AND SPmLMAN, D. 1991. PP is closed under intersection. In Proceedings of the 23rd Annual ACM Symposmm on the Theory of Computmg. ACM, New York, 1 9. The randomized complexity class PP is shown to be closed under intersection and union. Google ScholarDigital Library
BELLARE, M. AND MICALI, S. 1989. Non-interactive oblivious transfer and applications. In Advances in Cryptology-CRYPTO 89. Lecture Notes in Computer Science, vol. 435. Springer- Verlag, New York, 547-559. Based on a complexity assumption, Bellare and Micali show that it ~s possible to build public-key cryptosystems in which oblivious transfer is itself implemented without any interaction. Google ScholarDigital Library
BELLARE, M. AND PETRANK, E. 1992. Making zero-knowledge provers efficient. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 711-722. They prove that if a language possesses a statistical zero-knowledge proof then it also possesses a statistical zero-knowledge proof in which the prover runs in probabilistic polynomial time with an NP oracle. Previously, this was only known given the existence of one-way permutatmns. Google ScholarDigital Library
BELLARE, M., GOLDWASSER, S., LUND, C., AND RUSSELL, A. 1993. Efficient probabilistically checkable proofs and applications to approximation. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing ACM, New York, 294-304. Bellare et al. construct multiprover proof systems for NP which use only a constant number of provers to simultaneously achieve low error, low randomness, and low answer size. As a consequence, they obtain asymptotic improvements to approximation hardness results for a wide range of optimization problems. Google ScholarDigital Library
BELLARE, M., GOLDREICH, O., AND GOLDWASSER, S. 1990a. Randomness in interactive proofs. In Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 563-572. The power of randomness in interactive proof systems, m quantitative terms, is considered. A randomness-efficient error reduction technique for converting one proof system into another one using the same number of rounds is presented.Google ScholarDigital Library
BELLARE, M., MICALI, S, AND OSTROVSKY, R. 1990b. Perfect zero-knowledge in constant rounds. In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computmg. ACM, New York, 482 493. This paper contains the first constant-round solutions with no unproven assumptions for the problems of graph isomorphism and quadratic residuosity. Google ScholarDigital Library
BEN-DAViD, S., BORODIN, A., KARP, R. M., TARDOS, G., AND WIGDEi2~ON, A. 1990. On the power of randomization in online algorithms. In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing. ACM, New York, 379-386. They prove the existence of an efficient "simulation" of randomized on-line algorithms by deterministic ones, which is the best possible in the presence of an adaptive adversary. Google ScholarDigital Library
BEN-OR, M. 1985. Fast asynchronous Byzantine agreement (extended abstract). In Proceedings of the 4th Annual ACM Symposium on the Principles of Distributed Computing. ACM, New York, 149 151. This work extends Bracha's {1985} algorithm to asynchronous networks, initially obtaining a polynomial expected-time protocol. This protocol is refined with the recursive use of Bracha's techniques to get an O(logk n) algorithm, where k is a large constant. Google ScholarDigital Library
BEN-OR, M. 1983. Another advantage of free choice: Completely asynchronous agreement protocols. In Proceedings of the 2nd Annual ACM Symposium on the Principles of Dtstributed Computing. ACM, New York, 27-30. Ben-Or's probabilistic algorithm for asynchronous Byzantine agreement, discussed in Section 3.5, was one of the first published solutions to the problem, and it remains the simplest. Processes toss coins independently to reach consensus on a value. His algorithm requires that less than one-fifth of the processes are faulty for correctness to be guaranteed. The expected number of rounds is exponential in the number of processes n, but becomes a constant when the number of faulty processes is o(~). Google ScholarDigital Library
BEN-OR, M. AND LtNIAL, N. 1989. Collective coin flipping. In Advances in Computing Research 5: Randomness and Computation. JAI Press, Greenwich, Conn. Ben-Or and Linial consider the problem of obtaining a distributed coin toss, where each node is initially assigned either a head or a tail. The outcome of the distributed coin toss should not be affected by bias at individual nodes. To exclude the obvious trivial solution where each nonfaulty node picks a predetermined value, it is required that if every node changes its initial value, the result of the distributed coin toss should also change. An efficient solution is obtained under the assumption that unfair (faulty) nodes have complete knowledge of actions taken by all nodes.Google Scholar
BEN-OR, M., GOLDWASSER, S., K1LIAN, J., .~3~D WIGDERSON, A. 1988a. Multi-prover interactive proofs: How to remove the intractability assumptions. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing. ACM, New York, 113-131. A multiprover interactive proof model is proposed and its properties examined. Google ScholarDigital Library
BEN-OR, M., GOLDWASSER, S., AND WIGDERSON, A. 1988b. Completeness theorems for noncryptographic fault-tolerant distributed computation. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing. ACM, New York, I 10. The problem is the same as that in Chaum et al. {1988}, and the results obtained are similar. Google ScholarDigital Library
BENTLEY, J. 1980. Multidimensional divide-andconquer. Commun. ACM 23, 4, 214 229. This paper contains an n log(n) deterministic algorithm for finding nearest neighbors in two-dimensional space. Google ScholarDigital Library
BERLEKAMP, E. R. 1970. Factoring polynomials over large finite fields. Math. Comput. 24, 713-745. This paper presents algorithms for root finding and factorization, two problems in finite fields. The latter problem is reduced to the root-finding problem, for which a probabilistic algorithm is given. This paper is a precursor of Rabin {1980b}.Google ScholarCross Ref
BERNSTEIN, h.J. 1980. Output guards and nondeterminism in CSP. ACM Trans. Program. Lang. Syst. 2, 2 (Apr.), 234-238. Bernstein presents a distributed algorithm for CSP output guards based on priority ordering of processes. Google ScholarDigital Library
BERNSTErN, E. AND VAZrt~NI, U. 1993. Quantum complexity theory. In Proceedings of the 25th Annual ACM Sympostum on the Theory of Computing. ACM, New York, 11-20. A quantum Turing Machine, as originally formulated by Deutsch {1985}, may be thought of as a quantum physical analogue of a probabilistic Turing Machine: it has an infinite tape, a finite state control, and, in its most general form, produces a random sample from a probability distribution on any given input. Bernstein and Vazirani prove the existence of a universal quantum Turing Machine, whose simulation overhead is polynomially bounded. They also present the first evidence that quantum TMs might be more powerful than classical probabilistic TMs. Specifically, they prove that there is an oracle relative to which there is a language that can be accepted in polynomial time by a quantum TM but cannot be accepted in n~~l~g n~ time by a bounded-error probabilistic TM. Google ScholarDigital Library
BLUM, M. AND KANNAN, S. 1989. Designing programs that check their work. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. ACM, New York, 86-97. A more detailed version of Blum and Raghavan{1988}. Also see "Designing programs that check their work," Tech. Rep., Computer Science Div., Univ. of California, Berkeley. Google ScholarDigital Library
BLUM, M. AND MICALL S. 1984. How to generate cryptographically strong sequence of pseudorandom bits. SIAM J. Comput. 13, 4, 850-864. This paper introduces the notion of a cryptographically secure pseudorandom number generator. Google ScholarDigital Library
BLUM, M. AND RACHAV~, P. 1988. Program correctness: Can one test for it. Tech. Rep. RC 14038 (#62902), IBM T. J. Watson Research Center, Yorktown Heights, N.Y. They present "program checkers" for a number of interesting problems based on interactive proofs.Google Scholar
BLUM, A., KARLOFF, H., RABANI, Y., AND SAKS, M. 1992. A decomposition theorem and bounds for randomized server problems. In Proceedings of the 33rd Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 197 207. In a }~-aerver problem, each server is at some point in a metric space. At each time step, a request arises. Each request is a point in metric space and must be serviced by moving one of the k servers to the point specified. The cost associated with the request is the distance that the server moves. The competitive ratio of a k-server system is the worst-case ratio of the cost of an interactive algorithm on a sequence of inputs, to the optimal cost that would be incurred if the entire sequence were known in advance. The paper proves a lower bound of ll(~/log k/loglog k ) for the competitive ratio of a k-server system assuming an oblivious adversary. This improves on the previously known bound of i)(loglog k).Google ScholarDigital Library
BLUM, M., DESANTIS, A., MICALI, S., AND PERSIANO, G. 1991. Noninteractive zero-knowledge. SIAM J. Comput. 20, 6, 1084 1118. A key paper that summarizes the previous work on noninteractive zero-knowledge proofs. The concept of shared randomness is introduced, and how that can dispose of interaction between the prover and the verifier is illustrated. The authors show that noninteractive zero-knowledge proofs exist for some numbertheoretic languages for which no efficient algorithms are known. They also show that if quadratic residuosity is computationMly hard, satisfiability also has a noninteractive zero-knowledge proof. Google ScholarDigital Library
BLUM, M., LUBY, M., AND RUBINFELD, R. 1990. Self-testing/correcting with applications to numerical problems In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing. ACM, New York, 73 83. This paper is a more recent reference on the use of randomization in program testing and adds to the collection of interesting examples contained in Blum and Kannan {1989} and Blum and Raghavan { 1988}. Google ScholarDigital Library
BLUM, M., FELDMAN, P., AND MICALI, S. 1988. Non-interactve zero-knowledge proof systems and applications. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, ACM, New York, 103-112. This paper introduces the notion of noninterac~lve zero-knowledge proofs where the interaction between the prover and the verifier is replaced by shared, random strings. Google ScholarDigital Library
BLUM, M., BLUM, L., AND SHUB, M. 1986. A simple and secure pseudo-random number generator. SIAM J. Comput. 15, 2, 364 383. Two pseudorandom sequence generators are presented which, from small seeds, generate long well-distributed sequences. The first, the lip generator, is completely predictable from a small segment of its output. The second, the x2 (rood N) generator, is cryptographically secure since its sequence is polynomial-time unpredictable (if the quadratic residuosity problem is indeed hard). Google ScholarDigital Library
BOISSONNAT, J.-D. AND TEILLAUD, M. 1993. On the randomized construction of the Delaunay tree. Theor. Comput. Sci. 112, 2, 339-354. An on-line randomized algorithm which computes Delaunay triangulation and Voronoi diagrams of points in any number of dimensions is given. The complexity of the algomthm is optunal provided that the points are inserted in a random order. Google ScholarDigital Library
BOISSONNAT, J.-D., DEVILLERS, O., SCHOTT, R., TEILLAUD, M, AND YVINEC, M. 1992. Applications of random sampling to on-line algorithms in computational geometry. Discr. Comput. Geom. 8, 1, 51-71. This paper treats the same kind of problems as in Clarkson and Shor{1989}, but in a semidynamic way: the data can be initially unknown and added one by one. The analysis assumes that the points are inserted in a random order. Google ScholarDigital Library
BOPPANA, R.B. 1989. Amplification of probabilistic boolean formulas. In Advances in Computing Research 5: Randomness and Computation. JAI Press, Greenwich, Conn, 27-45. Valiant's{1984a} algorithm is shown to be the best possible. Also, an O(k43nlogn) algorithm for computing the kth threshold function of n variables is givenGoogle Scholar
BOPPANA, R. B. AND NARAYANAN, B.O. 1993. The biased coin problem. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing. ACM, New York, 252 257. A shghtly random source (with btas e) is a sequence x - (xt, x2,.., x~) of random bits such that the conditional probability that x, = 1, given the outcomes of the first ~ - i bits, is always between (1/2) - e and (1/2) + e. Given a subset S of {0, 1}", its e-b*ased probabd~ty is defined to be the mimmum of Pr{ x ~ S} over all slightly random sources x with bias e. The authors show that for every fixed e < 1/2 and almost every subset S of {0, 1}', the e-biased probablhty of S is bounded away from 0. They also show that there exists a perfectinformation, collective coin-flipping (leader election) protocol for n players that tolerates en cheaters, for every ~ < (2 1~ - 5)/3 = 0.44. Google ScholarDigital Library
BOPPANA, R., HAS?AD, J., AND ZACHOS, S. 1987 Does co-NP have short interactive proofs. Inf. Process. Lett 25, 2, 127 132. This important paper, along with Fortnow {1987}, provides a method of gaining high confidence that certain languages are not NP-complete. Google ScholarDigital Library
BORODIN, A., COOK, S. A., DYMOND, P. W., Ruzzo, W. L., AND TOMPA, M. 1989. Two applications of inductive counting for complementation problems. SIAM J. Comput. 18, 3 (June), 559-578. A probabilistic algorithm for s- t connectivity in undirected graphs is presented. Google ScholarDigital Library
BRiCHA, G. 1985. An O(log n) expected rounds randomized Byzantine generals protocol. In Proceedings of the 17th Annual Symposium on the Theory of Computing. ACM, New York, 316-326. Bracha shows how to partition a set of n synchronous processes (of which at most a third are faulty) into overlapping groups of processes such that the number of faulty groups ~s at most the square root the total number of groups. Ben-Or's algomthm for Byzantine agreement (see Section 3.5) is then used to obtain an O(log n) protocol. Google ScholarDigital Library
BRASSARD, G. AND BRATLEY, P. 1988. Algorithmics: Theory and Practzce. Prentice-Hall, Englewood Cliffs, N.J. This book contains a very nice chapter on probabilistic algorithms for a variety of problems such as numerical integration, sorting, and set equality. Google ScholarDigital Library
BRASSARD, G. AND CR~PEAU, C. 1986. Zero-knowledge simulation of boolean circuits. In Advances in Cryptology-CRYPTO 86. Lecture Notes in Computer Science, vol. 263. Springer- Verlag, New York, 223-233. An important result by Goldreich et al. {1991{ in the design of cryptographic protocols asserts that if oneway functions exist then every language in NP has a minimum-knowledge-confirming -interactive proof. This paper proves a similar result under the assumption that certain numbertheoretic computations are infeasible. Google ScholarDigital Library
BROOER, A. Z. 1989. Generating random spanning trees. In Proceedings of the 30th Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 442-453. This paper solves the problem of generating a spanning tree of a connected, undirected graph G which has the following special property: it is chosen uniformly at random from all possible spanning trees of G. The expected running time of the probabilistic algorithm is O(n log n) per generated tree for almost all graphs. It can be O(n3) per generated tree in the worst case.Google Scholar
BRODER, A.Z. 1986. How hard is it to marry at random. (On the approximation of the permanent). In Proceedings of the 18th Annual ACM Symposium on the Theory of Computing. ACM, New York, 50-58. This paper provides a fullpolynomial randomized approximation scheme (fpras) for approximating the permanent. Evaluating the permanent of a n X n matrix is equivalent to counting perfect matchings in an associated bipartite graph. The problem of approximately counting the perfect matchings in a graph is reduced to that of generating them uniformly. See Jerrum and Sinclair {1989} for the definition of fpras and other related material. An erratum can be found in Proceedings of the 20th Annual ACM Symposium on the Theory of Computing, 1988. Google ScholarDigital Library
BUCKLEY, G. N. AND SILBERSCHATZ, A. 1983. An effective implementation for the generalized input-output construct of CSP. ACM Trans. Program. Lang. Syst. 5, 2. They present a distributed algorithm for CSP output guards based on priority ordering of processes. Their algorithm has the property that two processes that can communicate and do not establish communication with a third process will communicate within a bounded time. Google ScholarDigital Library
CANETTI, R. AND GOLDREICH, O. 1990. Bounds on tradeoffs between randomness and communication complexity. In Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 766- 775. Instead of considering the qualitative question, "Is an algorithm deterministic or randomized?,'' the authors try to determine, quantitatively, how much randomization does an algorithm use. Tight lower bounds on the length of the random input of parties computing a function f--depending on the number of bits communicated and the deterministic complexity of f--are derived.Google ScholarDigital Library
CANETTI, R. AND RABIN, T. 1993. Fast asynchronous Byzantine agreement with optimal resilience. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing. ACM, New York, 42-51. The resilience of a protocol is the maximum number of faults in the presence of which the protocol meets its specification. It is known that no Byzantine agreement (BA) protocol for n players (either synchronous or asynchronous) can be In/3} resilient, and the only known (In/3} 1)-resilient BA protocol runs in expected exponential time. The authors show that there exists a fast (In/3) - 1)-resilient BA protocol by presenting a randomized protocol such that, with overwhelming probability, all the nonfaulty players complete execution of the protocol in constant expected time. Google ScholarDigital Library
CARMICHAEL, R. D. 1912. On composite numbers p which satisfy the Fermat congruence ap 1 _-p. Am. Math. Mon. 19, 2, 22-27. Let n = I~,-~n p? be the unique prime factorization of n, and let A(n)= lcm{p~~-l(pl- 1), , -1 .. p;," ( p,~ - 1)}. Carmichael shows that n satisfies Fermat's congruence if and only if i(n) divides (n - 1).Google Scholar
CARTER, J. L. AND WEGMAN, M.N. 1979. Universal classes of hash functions. J. Comput. Syst. Sci. 18, 2, 143-154. This paper contains the first discussion on universal hashing. An earlier version appeared in Proceedings of the 9th Annual ACM Symposium on the Theory of Computing, 1977, pp. 106-112. Google ScholarDigital Library
CASPL P., PIOTROWSrn, J., AND VELZACO, R. 1991. An a priori approach to the evaluation of signature analysis efficiency. IEEE Trans. Comput. 40, 9 (Sept.), 1068-1071. This paper presents an interesting application of control randomization for compressing the results from a digital circuit under test. Instead of imposing any distribution on the input sequence, the linear feedback shift register used for compression is chosen at random. Google ScholarDigital Library
CHANG, C.C. 1984. The study of an ordered minimal perfect hashing scheme. Commun. ACM 27, 4 (Apr.), 384-387. Chang uses hash functions of the form h(x) ~ (C rood p(x)) where C is an integer constant and where p(x) generates a different prime for each integer x. No general method for finding p(x) is given. Google ScholarDigital Library
CHANG, E. ANn ROBERTS, R. 1979. An improved algorithm for decentralized extrema finding in circular configurations of processors. Commun. ACM 22, 5 (May), 281-283. They present a deterministic distributed algorithm for finding the largest of a set of n uniquely numbered processes in a ring. The algorithm uses O(n log n) messages on the average and O(n2) messages in the worst case and does not assume that n is known a priori. Google ScholarDigital Library
CHARI, S., ROHATGI, P., AND SmmVASAN, A. 1993. Randomness-optimal unique element isolation, with applications to perfect matching and related problems. In Proceedings of the 25th Annual ACM Symposium on the Theory of Computing. ACM, New York, 458 467. The authors give a randomness-efficient RNC2 algorithm for perfect matching that uses O(log Z + log n) random bits, where Z is any given upper bound on the number of perfect matchings in the given graph. Google ScholarDigital Library
CHAUM, D., CR/~PEAU, C., AND DAMGXRD, I. 1988. Multiparty unconditionally secure protocols. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing. ACM, New York, 11-19. Assuming the existence of authenticated secrecy channels between each pair (P~, P,) of participants, this paper shows that if at least 2n/3 of the P~s are honest then a function f(xl, x2,.., x,), where x~ is known only to P, for each l, can be computed without any Pc revealing its information. Google ScholarDigital Library
CHAZELLE, B. AND FRIEDMAN, J. 1990. A deterministic view of random sampling and its use in geometry. Combinatorica 10, 3, 229-249. Using techniques due to Lov~sz and Spencer, the authors present a unified framework for derandomizing probabilistic algorithms that resort to repeated random sampling over a fixed domain. In the process, they establish results of independent interest concernmg the covering of hypergraphs. Specifically, via a modification of Lov~sz's greedy cover algortthm, they give an algorithm that, given a hypergraph with n vertices and m edges, each of size >_ an, computes an r-sample that intersects every edge e of the hypergraph in ll(le{r/n) vertices, where r = O((log n + log m)/c~ ). This improves upon Lov~sz's algorithm in terms of the number of covered vertices. The tools they use for computing covers "are powerful enough to derandomize just about every probabilistic algorithm proposed in computational geometry."Google ScholarCross Ref
CHERIYAN, J. 1993. Random weighted Laplacians, Lov~sz minimum digraphs and finding minimum separators. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 31-40. Cheriyan gives an O(n2aS)-time randomized algorithm for the problem of finding a minimum X- Y separator in a digraph and of finding a minimum vertex cover in a bipartite graph, thereby improving on the previous best bound of O(n2 S/log n). Google ScholarDigital Library
CHOR, B. AND COAN, B. 1985. A simple and efficient randomized Byzantine agreement algorithm. 1EEE Trans. Softw. Eng. SE-11, 6 (June), 531-539. Chor and Coan present a randomized algorithm for synchronous Byzantine agreement when n >_ 3t + 1, where n ~s the total number of processors and t is the number of faulty processors. Their algorithm reaches agreement in O(t/log n) expected rounds and O(n2t/log n) expected message bits, independently of the distribution of processor failures.Google ScholarDigital Library
CHOR, B. AND DWORK, C. 1989. Randomization in Byzantine agreement. In Advances tn Computtng Research 5: Randomness and Computation. JAI Press, Greenwich, Conn., 443 497. A useful survey of the myriad of randomized distributed algorithms for Byzantine agreement.Google Scholar
CHOR, B. AND GOLDRmCH, O. 1988. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM J. Comput. 17, 2, 230-261. Given sources of strings in which no string is "too probable," a method of extracting almost unbiased random bits is presented. Google ScholarDigital Library
CICHELLI, R. 1980 Minimal perfect hash functions made simple. Commun. ACM 23, 1 (Jan.), 17-19. A heuristic for computing a simple, fast, and machine-independent hash function is presented. Because of these properties, several attempts have been made to extend this paper since its publication. Google ScholarDigital Library
CLARKSON, K. L. AND SHOR, P.W. 1989. Apphcations of random sampling in computational geometry, II. Dtscr. Comput. Geom. 4, 5, 387-421. Efficient probabilistic algorithms are presented for the problems of line segment intersection, convex hull, polygon triangulation, and halfspaee partitions of point sets. Each algorithm is of the Las Vegas variety and uses the technique of random sampling. An earher version of this paper appeared in Proceedmgs of the 4th ACM Sympostum on Computattonal Geometry, 1988.Google ScholarDigital Library
COHEN, A. AND WIGDERSON, A. 1989. D~spensers, deterministic amplification, and weak random sources (extended abstract). In Proceedings of the 30th Annual IEEE Symposium on the Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, Calif., 14-25. The authors use highly expanding bipartite multigraphs (dispensers) to show that the error probabfilty of any RP or BPP algorithm can be made exponentially small in the size of the input at the cost of only a constant-factor increase in the number of random bits used by the algorithm. The simulation of these algorithms with weak sources of random numbers is also considered.Google Scholar
CONDON, A., FEIGENBAUM, J., LUND, C., AND SHOR, P. 1993. Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions. In Proceedings of the 25th Annual ACM Sympostum on the Theory of Computing. ACM, New York, 305 314 A probabilist~cally checkable debate system (PCDS) for a language L consists of a probabilistic polynomial-time verifier V and a debate between player 1, who claims that the input x is in L, and player 0, who claims that the input x is not in L. The authors show that there is a PCDS for L in which V flips O(log n) random coins and reads O(1) bits of debate if and only if L is in PSPACE. This characterization of PSPACE is used to show that certain PSPACE-hard functions are as difficult to approximate as they are to compute exactly. Google ScholarDigital Library
CORMEN, T. H., LEISERSON, C. E., AND RIVEST, R. L. 1990. Introduction to Algorithms. The MIT Press, Cambridge, Mass. This well-written encyclopedic introduction to algorithms covers a number of randomized algorithms including those for boolean matrix multiplication, binary search trees, primality testing, partitioning, universal hashing, and parallel prefix. Google ScholarDigital Library
CZECH, Z. J., HAVAS, G., AND MAJEWSKI, B.S. 1992. An optimal algorithm for generating minimal perfect hash functions. Inf. Process. Lett. 43, 5 (Oct.), 257-264. The authors describe a randomized algorithm for generating perfect hash functions that are space optimal and allow an arbitrary arrangement of keys in the hash table. The algorithm is based on the result of P. ErdSs and A. R~nyi {1960}, which states that the majority of random sparse 2-graphs are acyclic. The authors present a method of mapping a set of keys, using universal hash functions, into a random graph. Once the mapping is computed it is refined to a perfect hash function in linear deterministic time. The method strongly improves on the space requirements of the other probabilistic methods for generating minimal perfect hash functions. Google ScholarDigital Library
DAGUM, P., LUBY, M., MIHAIL, M., AND VAZIRANI, U.V. 1988, Polytopes, permanents and graphs with large factors. In Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 412-421. Randomized algorithms for approximating the number of perfect matchings in a graph based on a geometric reasoning are presented.Google ScholarDigital Library
DE LA VEGA, F., KANNAN, S., AND SANTHA, M. 1993. Two probabilistie results on merging. SIAM J. Comput. 22, 2, 261-271. Two probabilistic algorithms for merging two sorted lists are presented. When m < n, the first algorithm has a worst-case time better than any deterministic algorithm for 1.618 < n/m < 3. The algorithm is extended to perform well for any value of n/re. Google ScholarDigital Library
DE SANTIS, A. AND YUNG, M. 1990. Cryptographic applications of non-interactive metaproof~ and many-prover systems. In Advances in Cryptology-CRYPTO 90. Lecture Notes in Computer Science, vol. 537. Springer-Verlag, New York. The authors show how many provers can share the same random string in proving multiple theorems noninteractively in zero knowledge. Google ScholarDigital Library
DE SANTIS, A., M~CALL S., AND PERSIANO, G. 1988. Non-interactive zero-knowledge proof-systems with preproeessing. In Advances in Cryptology- CRYPTO 88. Lecture Notes in Computer Science, vol. 403, Springer-Verlag, New York, 269-283. The authors show that if any oneway function exists after an interactive preprocessing stage then any sufficiently short theorem can be proven noninteractively in zero knowledge. Google ScholarDigital Library
DE SANTIS, A., MICALI, S., AND PERSIANO, G. 1987. Non-interactive zero-knowledge proof-systems. In Advances in Cryptology-CRYPTO 87. Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 52-72. This paper introduces the notion of noninteractive zeroknowledge proofs based on a weaker complexity assumption than that used in Blum et al.{1988}. Google ScholarDigital Library
DEUTSCH, D. 1985. Quantum theory, the Church-Turing principle and the universal quantum computer. Proe. Royal Soc. London A400, 97-117. Deutsch introduces the quantum physical computer, later referred to as the "quantum Turing Machine" in Bernstein and Vazirani {1993}, which can be thought of as a quantum physical analogue of a probabilistic Turing Machine: it has an infinite tape, a finite state control, and, in its most general form, produces a random sample from a probability distribution on any given input.Google ScholarCross Ref
DEVILLERS, O. 1992. Randomization yields simple O(nlog*n) algorithms for difficult ~(n) problems. Int. J. Comput. Geom. Appl. 2, 1, 97 111. This papers provides two O(n log* n) randomized algorithms. One computes the skeleton of a simple polygon and the other the Delaunay triangulation of a set of points knowing the euclidean minimum spanning tree. The existence of deterministic O(n log n) algorithms for both problems is an open problem.Google ScholarCross Ref
DEVILLERS, O., MEISER, S., AND TEILLAUD, M. 1992. Fully dynamic Delaunay triangulation in logarithmic expected time per operation. Comput. Geom.: Theor. Appl. 2, 2, 55-80. This paper extends the results of Boissonnat and Teillaud{1993} by considering the deletion of points. The Delaunay triangulation of n points is updated in O(log n) expected time per insertion and O(log log n) expected time per deletion. The insertion sequence is assumed to be in a random order, and deletions are assumed to concern any currently present point with the same probability. Google ScholarDigital Library
DIETZFELBINGER, M. AND MEYER AUF DEe HEIDE, F. 1092. Dynamic hashing in foal t:~rne. In lnfor matik' Festschrift zum 60. Geburtstag yon Giinter Holtz, Teubner-Texte zur Informatik, Band 1. B. G. Teubner, Stuttgart, Germany, 95-119. The FKS probabilistic procedure is extended to real time. See Theorems 6.1 and 7.1 in Dietzfelbinger et al. {1992}. A preliminary version of this paper appeared as "A New Universal Class of Hash Functions and Dynamic Hashing in Real Time," Proceedtngs of the 17th Internattonal Colloquium on Automata, Languages and Programming, 1990, pp. 6-19. Google ScholarDigital Library
DIETZFELBINGER, M. AND MEYER AUF DER HEIDE, F. 1990. How to distribute a dictionary in a complete network. In Proceedtngs of the 22nd Annual ACM Symposium on the Theory of Computtng. ACM, New York, 117-127. A randomized algorithm is given for implementing a distributed dictionary on a complete network of p processors. The algorithm is based on hashing and uses O(n/p) expected time to execute n arbitrary instructions (insert, delete, lookup). The response time for each lookup is expected constant. Google ScholarDigital Library
DIETZFELBINGER, M., GIL, J., MATIAS, Y., AND PIPPENGER, N. 1992. Polynomial hash functions are reliable. In Proceedings of the 19th Internattonal Colloquzum on Automata, Languages and Programmtng. Lecture Notes in Computer Science, vol. 623. Springer-Verlag, New York, 235 246. This paper, along with Dietzfelbinger and Meyer auf der Heide {1992}, shows how to construct a perfect hash function in r(n) time, which is suitable for real-time applications (Theorems 6.1 and 7.1). Google ScholarDigital Library
DIETZFELBINGER, M., KARLIN, A., MEHLHORN, K., MEYER AUF DER HEIDE, F., ROHNERT, H., AND TAR JAN, R. E. 1988. Dynamic perfect hashrag: Upper and lower bounds. In Proceedings of the 29th Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 524 531. A randomized algorithm for the dictionary problem based on perfect hashing is presented.Google Scholar
DIJKSTRA, E. W. 1971. Hierarchical ordering of sequential processes. Acta Informattca 1, 2, 115 138. Reprinted in Operattng Systems Techniques, C. A. R. Hoare and R. H. Perrot, Eds., Academic Press, New York, 1972, pp. 72 93. This paper introduces the classical synchronization problem of dining philosophers.Google ScholarDigital Library
DOLEV, D. 1982. The Byzantine generals strike again. J. Alg. 3, 1, 14-30. This is an introductory paper on Byzantine Generals. Dolev p~ov~ that Ryzantino agroomont i~ aehi~vahl~ in any distributed system if and only if the number of faulty processors in the system is (1) less than one-third of the total number of processors and (2) less than one-half the connectivity of the system's network. In cases where agreement is achievable, deterministic algorithms for obtaining it are given.Google ScholarCross Ref
DWORK, C. AND STOCKMEYER, L. J. 1990. The time-complexity gap for 2-way probabilistic finite-state automata. SIAM J. Comput. 19, 6, 1011-1023. Among other results, this paper shows that any 2-way probabilistic finite automaton recognizing a nonregular language must use exponential expected time infinitely often. Since any regular language can be recognized in linear time, a time-complexity gap is established. Similar results were published in the paper entitled "On the Power of 2-Way Probabilistic Finite Automata," in Proceedmgs of the 30th Annual IEEE Symposium on the Foundattons of Computer Science, 1989. Google ScholarDigital Library
DWORK, C., SHMOYS, D., AND STOCKMEYER, L. 1990. Flipping persuasively in constant time. SIAM J. Comput. 19, 2, 472-499. An efficient randomized protocol is presented that tolerates up to n/(log n) malicious processors that requires constant expected number of rounds to achieve a distributed coin toss. Also given is a Byzantine Generals algorithm that tolerates n/(log n) failures and runs in constant expected number of rounds. A preliminary version of this paper appeared in Proceedings of the 27th Annual IEEE Symposium on the Foundations of Computer Science, 1986. Google ScholarDigital Library
DWORK, C., KANELLAKIS, P. C., AND STOCKMEYER, L.J. 1988. Parallel algorithms for term matching. SIAMJ. Comput. 17, 4, 711 731. In the context of a parallel algonthm for the term-matching problem, this paper shows how randomization can be used to reduce the initial processor complexity from O(n5) to O(M(n)), where M(n) is the processor complexity of multiplying two n x n matrices. Google ScholarDigital Library
DYER, M., FRIEZE, A., AND KANNAN, R. 1991. A random polynomial time algorithm for approximating the volume of a convex body. J. ACM 38, 1, 1-17. A constant-time oracle is assumed for determining if a point in space is inside or outside a convex body in n-dimensional Euclidean space. The algorithm runs in time bounded by a polynomial in n, the dimension of the body, and l/e, where e is the relative error bound With probability 3/4, it finds an approximation satisfying the error bound. Google ScholarDigital Library
ERD(~S, P. AND RgNYL A. 1960. On the evolution of random graphs. Pub. Math. Inst. Hung. Acad. Sct. 5, 1, 17-61. A seminal paper on random graphs. Reprinted in Paul ErdSs: The Art of Counttng. Selected Wrttings, J. H. Spencer, Ed., Mathematicians of Our Time, vol. 5, MIT Press, Cambridge, Mass., 1973, pp. 574-617.Google Scholar
ERD~S, P. AND SPENCER, J. 1974. Probabthsttc M~thod~ in Combinatorie~. Acadomic Press. New York. Recognized experts in the field present a small, power-packed monograph on nonconstructive probabilistic methods in combinatorics. Our algorithm for networks without large hierarchies is based on the discussion in Chapter 1 of this book. Other highlights include Ramsey's theorems and evolution of random graphs.Google Scholar
FEIGE, U. AND SHAMIR, A. 1992 Multiple oracle interactive proofs with constant space verifiers. J. Comput. Syst. Sct. 44, 2, 259-271. The authors show that the expected payoff of reasonable games of incomplete information are undecidable. The Turing-machine simulation uses polynomial cost and stops with probability 1. Google ScholarDigital Library
FE~GE, U., LAPIDOT, D., AND SHAMm, A. 1990. Multiple non-interactive, zero-knowledge proofs based on a single random string. In Proceedings of the 31st Annual IEEE Sympostum on the Foundations of Computer Science. IEEE, New York, 308-317. The following two problems posed in De Santis et al. {1988}, associated with noninteractive zero-knowledge proof systems, are solved: (1) how to construct NIZK proofs under general complexity assumptions rather than number-theoretic assumptions and (2) how to enable multiple provers to prove, in writing, polynomially many theorems based on a single random string. The authors show that any number of provers can share the same random string and that any trap-door permutation can be used instead of quadratic residuosity. Also, if the prover is allowed to have exponential computing power, then one-way permutations are sufficient for bounded noninteractive zero-knowledge proofs.Google Scholar
FE~GE, U., FIAT, A., ANo SHAMm, A. 1987. Zeroknowledge proofs of identity. In Proceedings of the 19th Annual ACM Sympostum on the Theory of Computing. ACM, New York, 210-217. Zero-knowledge proofs, in the traditional sense, reveal I bit of information to the verifier, viz., w ~ L or w ~ L. This paper proposes the notion of "truly zero-knowledge" proofs where the prover convinces the verifier that he/she knows whether w is or is not in L, without revealing any other information. An RSA-like scheme based on the difficulty of factoring, which is much more efficient than RSA, is also presented. Google ScholarDigital Library
FERRENBERG, A. M., LANDAU, D. F., AND WONG, Y. ~. 1992. Monte Carlo simulations: Hidden errors from "good" random number generators. Phys. Rev. Lett. 69, 23 (Dec.), 3382-3388. The authors unveil subtle correlations in five widely used pseudorandom number generators. They undertook this investigation when a simple mathematical model of the behavior of atoms in a magnetic crystal failed to give the expected results. They traced the error to the pseudorandom number generator used in the simulation.Google ScholarCross Ref
FEYNMAN, R. P. 1982. Simulating physics with computers. Int. J. Theoret. Phys. 21, 6/7, 467-488. Feynman points out the curious problem that it appears to be impossible to simulate a general quantum physical system on a probabilistic Turing Machine without an exponential slowdown, even if the quantum physical system to be simulated is discrete (like some kind of quantum cellular automaton).Google ScholarCross Ref
F~SCHER, M. J. AND LYNCH, N. 1982. A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14, 4, 182-186. They prove that no deterministic solution to the Byzantine Generals problem can reach agreement in less than t + i rounds, where t is the number of faulty processes.Google Scholar
FrSCHER, M. J., LYNCH, N., AND PATERSON, M. 1985. Impossibility of distributed consensus with one faulty process. J. ACM 32, 2 (Apr.). This paper proves that every completely asynchronous, deterministic algorithm for Byzantine agreement has the possibility of nontermination, even with only one faulty processor. This impossibility result does not hold in the synchronous case. For completely asynchronous probabil~stic algorithms, the problem is avoided since termination is only required with probability 1. See Section 3.5 for an example of such a probabilistic algorithm for asynchronous Byzantine agreement. Google ScholarDigital Library
FLAJOLET, P. 1990. On adaptive sampling. Computing 43, 4, 391-400. Adaptive sampling is a probabilistic technique due to Wegman that allows one to estimate the cardinality (number of distinct elements) of a large file typically stored on disk. This problem naturally arises in query optimization of database systems. Flajolet shows that using m words of in-core memory, adaptive sampling achieves an expected relative accuracy close to 1.20/~fm. This compares well with the probabilistic counting technique of Flajolet and Martin {1985b}: adaptive sampling appears to be about 50% less accurate than probabilistic counting for comparable values of m. Adaptive sampling, however, is completely free of nonlinearities for smaller values of cardinalities (probabilistic counting is only asymptotically unbiased). Google ScholarDigital Library
FLAJOLET, P. 1985. Approximate counting: A detailed analysis. BIT 25, 1, 113-134. In 1978, R. Morris published an article in Commun~ca~ tions of the ACM entitled "Counting Large Numbers of Events in Small Registers." It presented a randomized algorithm, known as Approximate Counting, that allows one to approximately maintain a counter whose values may range in the interval I to M using only about log log M bits, rather than the log M bits required by a standard binary counter. The algorithm has proven useful in the areas of statistics and data compression. Flajolet provides a complete analysis of approximate counting which shows (among other things) that, using suitable corrections, one can count up to M keeping only loglog M + 3 bits with an accuracy of order 0(2 ~/2). Google ScholarDigital Library
FLAJOLET, P. ANn MARTIN, G. N. 1985a. Probabilistic counting algorithms for data base appli~ cations. J. Comput. Syst. Sci. 25, 31, 182-209. This paper presents a probabilistic counting technique for determining the number of distinct records in a file. Google ScholarDigital Library
FLAJOLET, P. AND MARTIN, G. N. 1985b. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31, 2, 182-209. Probabilistic counting is a technique for estimating the cardinality (number of distinct elements) of a large file typically stored on disk. This problem naturally arises in query optimization of database systems. Using m words of in-core memory, probabilistic counting achieves an expected relative accuracy close to 0.78/~-. Moreover, it performs only a constant number of operations per element of the file. The technique requires O(1) storage and a single pass over the file. It also appeared as "Probabilistic Counting," Proceedings of the 24th Annual IEEE Symposium on the Foundations of Computer Science, 1983, pp. 76-84. Google ScholarDigital Library
FORTNOW, L. 1987. The complexity of perfect zero-knowledge. In Proceedings of the 19th Annual ACM Symposium on the Theory of Computing. ACM, New York, 204 209. The notion of perfect zero knowledge requires that the verifier, no matter how powerful it is, not learn any additional information. Fortnow proves, that for any language which has a perfect zero-knowledge protocol, its complement has a single-round interactive protocol. This result implies that for NP-complete languages, there are no perfect zero-knowledge protocols (unless the polynomial-time hierarchy collapses). Google ScholarDigital Library
Fox, E., HEATH, L. S., CHEN, Q. F., AND DAOUU, A. 1992. Practical minimal perfect hash functions for large databases. Commun. ACM 35, 1 (Jan.), 105-121. This paper presents two randomized algorithm for minimal perfect hashing functions that are designed for use with databases with as many as a million keys. The algorithms have been experimentally evaluated. The first algorithm generates hash functions that are less than O(n) computer words long, and the second generates functions that approach the theoretical lower bound of D,(n/ log n) words. This work is a predecessor of Fox et al. {1991}. Google ScholarDigital Library
Fox, E., CHEN, Q. F., DAOUD, A., AND HEATH, L. S. 1991. Order preserving minimal perfect hash functions and information retrieval. ACM Trans. Inf. Syst. 9, 2 (July), 281 308. This algorithm combines the techniques of embedding the keys into an r graph and two-level hashing to design hash functions that are optimal in terms of hashing time and space utilization. The algorithm to generate the hash functions uses near-optimal space and time. Any desired order can be maintained. Google ScholarDigital Library
FRANCEZ, N. AND RODEH, M. 1980. A distributed abstract data type implemented by a probabilistic communication scheme. In Proceedings of the 21st Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 373-379. They also give a deadlock-free, truly distributed and symmetric solution to the dining philosophers problem based on a probabilistic implementation of CSP. In particular, they present a randomized algorithm for the scheduling of input/output guards in CSP, which we discuss in Section 3.2. This was one of the first papers on probabilistic distributed algorithms. A revised version appears as TR 80, IBM Scientific Center, Haifa, Israel, April, 1980 (same title).Google ScholarDigital Library
FREDMAN, M. L., KOMLdS, J., AND SZEMEREDI, E. 1982. Sorting a sparse table with O(1) worst case access time. In Proceedings of the 23rd Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 165- 169. This paper proves many fundamental results that are essential for constructing a perfect hashing function for a given set of keys.Google ScholarDigital Library
FIJRER, M., GOLDREICH, O., MANSOUR, Y., SIPSER, M., AND ZACHOS, S. 1989. On completeness and soundness in interactive proof systems. In Advances in Computing Research 5: Randomness and Computation JAI Press, Greenwich, Conn., 429 442. An interactive proof system for a language L is said to have perfect completeness if the verifier always accepts w if w c L This paper proves that any language having an interactive, posmbly unbounded proof has one with perfect completeness. Only languages in NP have interactive proofs with perfect soundness. This paper first appeared under the title "Interactive Proof System: Provers that Never Fail and Random Selection," by O. Goldreich, Y. Mansour, and M. Sipser, in Proceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science, 1987, pp. 449-461.Google Scholar
GALm, Z., HABER, S., AND YUNG, M. 1989. Minimum-knowledge interactive proofs for decision problems. SIAM J. Comput 18, 4 (Aug.), 711-739. This paper extends the work of Goldwasser et al. {1989}; the concept of minimum knowledge is defined, and a minimumknowledge protocol for transferring the results of any fixed computation from one party to another (e.g. prover to verifier) is described. Google ScholarDigital Library
GAllEY, M. R. AND JOHNSON, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York. This well-known book on the theory of NP-completeness contains a section on the probabilistic analysis of approximation algorithms for NP-complete combinatorial optimization problems. Google ScholarDigital Library
GAZIT, I-I. 1991. An optimal randomized parallel algorithm for finding the connected components of a graph. SIAM J. Comput. 20, 6, 1046-1067. The expected running time of this algorithm is O(log n) with O((m + n)/log n) processors, where n is the number of' vertices and m the number of edges. It uses O(m + n) space. The algorithm is optimal in the time processor product sense, as well as m space complexity. Google ScholarDigital Library
GERgB-GRAuS, M. AND KmZANC, D. 1992 The average complexity of parallel comparison merging. SIAM J. Comput. 21, 1, 43 47. The authors establish a lower bound on the time complexity of randomized merging of two sorted lists in a parallel-computation tree model. An earlier version of this paper, entitled "The Complexity of Parallel Comparison Merg/ng," appeared in Proceedings of the 28th Symposium on the Foundations of Computer Science, 1987. Google ScholarDigital Library
GmL, J. T. 1977. Computational complexity of probabilistic Turing machines. SIAM J. Cornput. 6, 4 (Dec.), 675-695. This paper defines the basic notion of a probabilistic Turing machine (PTM). A PTM computes a partial function that assigns to each input the output which occurs with a probability greater than half. It is shown that an NDTM can be simulated by a PTM in the same space but with a small error probability. Gill also considers the complexity classes RP, PP, and BPP for polynomial-time probabilistic Turing Machines (see Section 4.1). He shows that P c RP c BPP C PP C PSPACE and that RP c NP c PP.Google Scholar
GODDARD, W., KING, V., AND SCHULMAN, L. 1993. Optimal randomized algorithms for local sorting and set-maxima. SIAM J. Comput. 22, 2, 272-283. Nearly optimal randomized algorithms are presented for the local sorting problem (i.e., determining the relative order in every pair of adjacent vertices in a graph in which each vertex is assigned an element of a total order) and the set-maxima problem (i.e., determining the maximum element of each set in a collection of sets whose elements are drawn from a total order). Google ScholarDigital Library
GOLDREICH, O., MICALI, S., AND WIGDERSON, A. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 1, 691-729. They show that for a language L in NP and a string w in L, there exists a probabilistic interactive proof that efficiently demonstrates membership of x in L without conveying additional information. Previously, zero-knowledge proofs were known only for some problems that were in both NP and co-NP. A preliminary version of this paper appeared in Proceedings of the 27th Annual IEEE Sympostum on the Foundations of Computer Science, 1986, under the title "Proofs that Yield Nothing but their Validity and a Methodology of Cryptographic Protocol Design." Google ScholarDigital Library
GOLDREICH, O., MICALI, S., AND WIGDERSON, A. 1987. How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the 19th Annual ACM Symposium on the Theory of Computing. ACM, New York, 218-229. Goldreich et al. demonstrate the use of zero-knowledge proofs on proving the completeness theorem for protocols with honest majority. Google ScholarDigital Library
GOLDREICH, O., GOLDWASSER, S., AND MICALI, S. 1986. How to construct random functions. J. ACM 33, 4, 792-807. A computational complexity measure of the randomness of functions is introduced, and, assuming the existence of oneway functions, a pseudorandom function generator is presented. Google ScholarDigital Library
GOLDWASSER, S. AND KILIAN, J. 1986. Almost all primes can be quickly certified. In Proceedings of the 18th Annual ACM Symposium on the Theory of Computing. ACM, New York, 316- 329. The authors show that if Cram6r's conjecture about the spacing of prime numbers is true then there exists a random polynomialtime algorithm for primality testing. Google ScholarDigital Library
GOLDWASSER, S. AND MACALI, S. 1984. Probabilistic encryption. J. Comput. Syst. Sci. 28, 2, 270-299. This paper introduces a new probabilistic encryption technique. It also contains an excellent introduction to other public-key cryptosystems with discussion on objections to cryptosystems based on trap-door functions.Google ScholarCross Ref
GOLDWASSER, S. AND SIPSER, M. 1989. Private coins versus public coins in interactive proof systems. In Advances in Computing Research 5: Randomness and Computation, S. Micali, Ed. JAI Press, Greenwich, Conn. This work establishes equivalence between the notions of interactive proofs introduced in Babai and Moran {1988} and Goldwasser et al. {1989}. A preliminary version appeared in Proceedings of the 18th Annual ACM Symposmm on the Theory of Computing, 1986, pp. 59-68. Google ScholarDigital Library
GOLDWASSER, S., MACALI, S., AND RACKOFF, C. 1989. The knowledge complexity of interactive proof systems. SIAMJ. Comput. 18, 1, 186-208. This paper first appeared in Proceedings of the 17th Annual ACM Symposium on the Theory of Computing. ACM, New York, 291-304. It introduces the important notion of zeroknowledge interactive proofs. The authors show that it is possible to prove that certain theorems are true without divulging why this is so. Google ScholarDigital Library
GOLDWURM, M. 1992. Probabilistic estimation of the number of prefixes of a trace. Theoret. Comput. Sci. 92, 2, 249-268. The author uses the result to determine the behavior of several algorithms relating to trace languages. Google ScholarDigital Library
GOLIN, M., RAMA~, R., SCHWARZ, C., AND SMID, M. 1993. Randomized data structures for the dynamic closest-pair problem. In Proceedings of the 4th Annual ACM-SIAM Sympostum on Dtscrete Algorithms. ACM, New York, 301-310. The authors describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure, the closest pair of a set of n points in k-dimensional space, for any fixed k, can be found in constant time. If the points are chosen from a finite universe, and if the floor function is available at unit cost, then the data structure supports insertions into and deletiona from the set in expected O(log n) time and requires expected O(n) space. Here, it is assumed that the updates are chosen by an adversary who does not know the random choices made by the data structure. Google ScholarDigital Library
GONNET, G. H. AND BAEZA-YATES, R. 1991. Handbook of Algorithms and Data Structures. Addison-Wesley, Reading, Mass. Section 3.3A6 gives an overview of perfect hashing. Google ScholarDigital Library
GRAHAM, R. AND YAO, A. 1989. On the improbability of reaching Byzantine consensus. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. ACM, New York, 467-478. The maximum probability fi~,t of obtaining consensus is attacked for t >_ n/3. (For smaller values, deterministic algorithms are available, so 13,, t = 1.) The smallest nontmvial case fi3 l, is shown to be (~f5 - 1)/2, the reciprocal of the golden ratio. In a restricted model, it is shown that for all e, 0< e< 1, if t/n> 1-(1-1ogl- el/2)/ (log(1 - (1 - e)l/~)), then /3~,t < e. Google ScholarDigital Library
GREENBER% R. h AND LmSERSON, C. E. 1989. Randomized routing on fat-trees. In Advances in Computing Research: Randomness and Computation. JAI Press, Greenwmh, Conn., 345-374. Fat-trees are a class of routing networks in parallel computation. Given a set of messages to send, the choice is made at random of which message is to be sent at what time. This approach is different from that of Valiant { 1982}. See also Proceedings of the 17th Annual ACM Symposzum on the Theory of Computing, 1985, pp. 241-249.Google Scholar
GUmAS, L. J., KNUTH, D. E., AND SHARm, M. 1992~ Randomized incremental construction of Delaunay and Voronoi diagrams. Algorithm~ca 7, 4, 381 413. They give a new randomized incremental algorithm for the construction of planar Voronoi diagrams and Delaunay triangulations. Their algorithm takes expected time O(n/log n) and space O(n), is very practical to implement, and along with the algorithm of Boissonnat and Teillaud {1993}, is more "on-line" than earlier similar methodsGoogle ScholarCross Ref
GUPTA, R. 1993. ~-test: Perfect hashed index test for response validation. In Proceedings of the 1993 IEEE Internatmnal Conference on Computer Design. IEEE, New York. A scheme for checking the fidelity of test responses generated by a specially tailored sequence of test inputs is described. Randomized search is used to compute a special perfect hashing function htx) that maps the expected test outcomes to the sequence {1..m}. This sequence is checked by a hardware implementation of h(x ) and an up-counter.Google ScholarCross Ref
HADZILACOS, V. 1986. Ben-Or's randomized protocol for consensus in asynchronous systems. Course notes: Computer Science 2221F, Dept. of Computer Science, Univ. of Toronto, Toronto, Canada. An elegant proof of the correctness of Ben-Or's {1983} probabilistlc algorithm for Byzantine agreement is presented.Google Scholar
HALTON, J. H. AND TERADA, R. 1982. A fast algorithm for the euclidean traveling salesman problem, optimal wltb probability one. SJA~ J. Comput. 11, 1 (Feb.). Halton and Terada present an algorithm for the traveling salesman problem over n points, which, for appropriate choice of a function ~r takes less than n~r(n) time and asymptotically converges to the minimum-length tour, with probability one, as n -) co.Google Scholar
HAREL, D. 1987. Algorzthmzcs: The Spirit of Computing. Addison-Wesley, Reading, Mass. This book contains a well-written chapter on probabilistic algorithms and their complexity theory. Google ScholarDigital Library
HASTAD, J. 1990. Pseudo-random generators under uniform assumptions. In Proceedings of the 22nd Annual ACM Symposmm on the TheolTy of Computing. ACM, New York, 395 404. Hastad proves that given a functmn f that is one-way in the uniform model (i.e., cannot be inverted except on a vanishing fraction of the inputs by a probabilistic polynomial-time Turing Machine), it is possible to construct a pseudorandom bit generator that passes all probabilistic polynomial-time statistmal tests. Google ScholarDigital Library
HOARE, C. A. R. 1985. Communicating Sequential Processes. Prentice-Hall International, London, U.K. Hoare's book contains an elegant message-passing solution to the dining philosophers problem. A probabilistic algorithm for this problem is the subject of Section 3.1. Google ScholarDigital Library
HOARE, C. A. R. 1978. Communicating sequential processes. Commun. ACM 21, (Aug.), 666 677. Hoare's novel language CSP combined nondeterminism and synchronized message passing. Since its inception, various schemes have been proposed to add output guards to the language. In Section 3.2, we discuss a probabihstic algorithm for output guards. Google ScholarDigital Library
HOARE, C. A. R. 1974. Monitors: An operating system structuring concept. Commun. ACM 17, 2 (Oct.), 549 557. Erratum in CommunzcatmT~s of the ACM, Vol 18, No. 2, 1975. This paper contains one of the first solutions to the dining philosophers problem. A probabilistic algorithm for this problem is the subject of Section 3.1. Google ScholarDigital Library
HOPCROFT, J.E. 1981. Recent directions in algorithmic research. In Proceedings of the 5th Conference on Theoretzcal Computer Science. Springer-Verlag, New York, 123 134. This work is an early survey of probabilistic algorithms. Google ScholarDigital Library
IMPAGLIAZZO, E. AND ZUCKERMAN, D. 1989. How to recycle random b~ts. In Proceedings of the 30th Annual IEEE Symposzum on the Foundations of Computer Science. IEEE, New York, 248-253. This paper proves that two very simple pseudorandom number generators, which are minor modifications of the linear congruential generator and the simple shift register generator, are good for amplifying the correctness of probabilistic algorithms.Google ScholarDigital Library
IMPAGLIAZZO, R., LEVlN, L., AND LUBY, M. 1989. Pseudorandom generation from one-way functions. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. ACM, New York, 12-24. The existence of one-way functions is shown to be necessary and sufficient for the existence of pseudorandom generators. A one-way function F(x) is one that is easily computed, but given F(x), it should not be possible to easily recover x, either with a small circuit or with a fast algorithm. Algorithms for pseudorandom generators are provided that use one-way functions whose inverses are difficult to obtain using small circuits or fast algorithms. See also Hastad{1990}. Google ScholarDigital Library
ITAI, A. AND RODEH, M. 1981. The lord of the ring or probabilistic methods for breaking symmetry in distributed networks. Tech. Rep. RJ 3110, IBM, San Jose, Calif. Itai and Rodeh consider the problems of choosing a leader and determining the size of a ring of indistinguishable processors. If the size of the ring is known, efficient probabilistic algorithms exist for choosing a leader. However, there exists no probabilistic solution to the problem of determining the size of a ring that can guarantee both termination and a nonzero probability of correctness.Google Scholar
JAESCHKE, G. 1981. Reciprocal hashing: A method for generating minimal perfect hashing functions. Commun. ACM 24, 12 (Dec.), 829-823. Hash functions, for a key x in a set S of positive integers, of the form h(x) = (C/ (Dx + E)) mod N are considered. Though the existence of h is guaranteed, the scheme suffers from many practical problems because of the exhaustive nature of the search for h. Google ScholarDigital Library
JERRUM, M. R. AND S~NCLAm, A. 1989. Approximating the permanent. SIAM J. Comput. 18, 6, 1149-1178. Broder {1986} related the task of approximating the permanent of a matrix to that of uniformly generating perfect matchings in a graph. This paper gives a randomized approximation scheme for the latter problem by simulating it as a Markov chain whose states are matchings in the graph. For this scheme to be efficient the Markov chain must be rapidly mixing, i.e., converge to its stationary distribution in a short time. Google ScholarDigital Library
JERRUM, M. R., VALIANT, L. G., AND VAZI~NI, V. V. 1986. Random generation of combinatorial structures from a uniform distribution. Theoret. Comput. Sc~. 43, 2/3, 169-188. This paper considers the class of problems involving the random generation of combinatorial structures from a uniform distribution. It is shown that exactly uniform generation of "efficiently verifiable'' combinatorial structures is reducible to approximate counting. Google ScholarDigital Library
JOHNSON, D. S. 1990. A catalog of complexity classes. In Handbook of Theoretical Computer Sczence. Vol. A. Algorithms and Complexity. Elsevier and The MIT Press, New York/Cambridge, Mass., 67-161. Johnson presents an extensive survey of computationalcomplexity classes. Of particular interest here is his discussion of randomized, probabilistic, and stochastic complexity classes. Google ScholarDigital Library
KALAI, G. 1992. A subexponential randomized simplex algorithm. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 475-482. A randomized variant of the simplex algorithm is presented that, given a linear program with d variables and n constraints, uses an expected subexponential number of arithmetic operations. Google ScholarDigital Library
KAO, M.-Y., RErF, J. H., AND TATE, S. R. 1993. Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 441-447. The first randomized algorithm for the w-lane cow path problem, a problem of searching in an unknown environment, is given. The algorithm is optimal for w = 2, and evidence is supplied that it is optimal for larger values of w. Google ScholarDigital Library
KARGER, D. R. 1993. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the 4th Annual ACM-S{AM Symposium on D~screte Algorithms. ACM, New York, 21 30. Given a graph with n vertices and m (possibly weighted) edges, the min-cut problem is to partition the vertices into two nonempty sets S and T so as to minimize the number of edges crossing from S to T (if the graph is weighted, the problem is to minimize the total weight of crossing edges). Karger gives an RNC algorithm for the rain-cut problem which runs in time O(log2 n) on a CRCW PRAM with mn2 log n processors. Google ScholarDigital Library
KARGER, D. R. AND STEIN, C. 1993. An ()(n2) algorithm for minimum cuts. In Proceedings of the 25th Annual ACM Symposium on the Theor)/of Computing. ACM, New York, 757-765. A mimmum cut is a set of edges of minimum weight whose removal disconnects a given graph. Karger and Stein give a strongly polyno~ mial randomized algorithm which finds a minimum cut with high probability in O(n2 log3 n) time. Their algorithm can be implemented in RNC using only n2 processors and is thus the first efficient RNC algorithm for the rain-cut problem. Google ScholarDigital Library
KARLOFF, H. AND RAGHAVAN, P. 1988. Randomized algorithms and pseudorandom numbers. In Proceedings of the 20th Annual ACM Symposium on the Theory of Computing. ACM, New York, 310 321. Following up on Bach {1991}, this paper studies pseudorandom substitutes (with small seeda) for purely random choices in sorting, selection, and oblivious-message routing. An interesting result is that the linearcongruence pseudorandom number generator proposed by Knuth {1973} can interact with some quicksort algorithms. Google ScholarDigital Library
KARP, R.M. 1991. Probabilistic recurrence relations. In Proceedings of the 23rd Annual ACM Symposium on the Theory of Computing. ACM, New York, 190 197 In order to solve a problem instance of size x, a divide-and-conquer algorithm invests an amount of work a(x) to break the problem into subproblems of sizes hi(x), h2lx) ... hk(x), and then proceeds to solve the subproblems. When the h~ are random variables--because of randomization within the algorithm or because the instances to be solved are assumed to be drawn from a probability distribution--the running time of the algorithm on instances of size x is also a random variable T(x). Karp gives several easyto-apply methods for obtaining fairly tight bounds on the upper tails of the probability distribution of T(x) and presents a number of typical applications of these bounds to the analysis of algorithms. The proofs of the bounds are based on an interesting analysis of optimal strategies in certain gambling games. Google ScholarDigital Library
KARP, R. M. 1990. An introduction to randomlzed algorithms. Tech. Rep. TR-90-024, Computer Science Div., Univ. of California, Berkeley. A recent, comprehensive survey of randomized algorithms.Google Scholar
KARP, R.M. 1986. Combinatorics, complexity and randomness. Commun. ACM 29, 2 (Feb.), 98-109. This is the 1985 Turing Award Lecture. It traces the development of combinatorial optimization and computational complexity theory. It discusses probabilistic algorithms and probabilistic analysis of approximation algorithms for NP-complete optimization problems. Google ScholarDigital Library
KARP, R. M. AND LUBY, M. 1985. Monte-Carlo algorithms for planar multiterminal reliability problems. J. Complex. 1, 1, 45-64. They present a general Monte Carlo technique for obtaining approximate solutions of several enumeration and reliability problems including: counting the number of satisfying assignments of a propositional formula given in disjunctive normal form (a #P~complete problem) and estimating the failure probability of a system. An earlier version appeared in Proceedings of the 24th Annual IEEE Symposium on the Foundations of Computer Science, 1983, pp. 56 64. See Karp et al. {1989}.Google ScholarCross Ref
KARP, R_ M. AND RABIN. M_ O. 1987. Efficient randomized pattern-matching algorithms. IBM J. Res. Devel. 31, 2 (Mar.), 249-260. An elegant randomized algorithm for the string-matching problem is presented. Mismatches reported by the algorithm are always correct, while a claimed match may be erroneous with small probability. The algorithm uses a fingerprinting function (on the finite field of mod p residues, where p is chosen at random) to efficiently check for occurrences of the pattern string in the text string. The running time of the algorithm is O((n m + 1)m) in the worst case, where the text is of length n and the pattern is of length m, but can be expected to run in time O(n + m) in practice. The probability that the algorithm reports a false match is 1/n. Two-dimensional patterns are also considered. An earlier version of this paper appeared as Tech. Rep. TR-31-81, Aiken Computation Lab, Harvard Univ., 1981. Google ScholarDigital Library
KA~P, R. M. AND WICDERSON, A 1985. A fast parallel algorithm for the maximal independent set problem. J. ACM 32, 4, 762 773. This important paper showed that the maximal independent-set problem for graphs can be solved in polylogarithmic time using a polynomial number of processes on a PRAM in which concurrent reads and writes are disallowed. They derive their algorithm from a randomized one using a technique that has become known as derandomization via k-wise independence. Google ScholarDigital Library
KARP, R. M., LUBY, M., AND MEYER AUF DER HEIDE, F. 1992. Efficient PRAM simulation on a distributed memory machine. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 318 326. They present a randomized simulation of an n log log(n)log*(n)-processor shared-memory machine (PRAM) on an nprocessor distributed-memory machine (DMM) with optimal expected delay O(loglog(n)log* (n)) per step of simulation. Google ScholarDigital Library
KARP, R M., LUB~, M., AND MA~P~S, N. 1989. Monte-Carlo approximation algorithms for enumeration problems. J. Alg. 10, 3, 429 448. A companion paper of Karp and Luby {1985}; an earlier version appeared in Proceedings of the 24th Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 56-64. Google ScholarDigital Library
KARP, R. M., UPFAL, E., AND WIGDERSON, A. 1986. Constructing a perfect matching in Random NC. Combmator~ca 6, 1, 35-48. Perfect matching is a fundamental problem that is not known to be solvable by an NC algomthm, i.e., a parallel algorithm running in time polynomial in log n and using a number of processors polynomml in n. This paper proves that perfect matching is m random NC and gives a fast, parallel, randomized algorithm for finding a perfect matching in a simple graph. Google ScholarDigital Library
KARP, R. M., PIPPENaER, N., AND SIPSER, M. 1985. A time randomness tradeoff. In {he AM~ Conference on Probabihstic Computatzonal Complexity. AMS, New York. This paper gives the first example of deterministic amplification using expander graphs.Google Scholar
KEDEM, Z. M., PALEM, K. V., RABIN, M. O., AND RAGHUNATHAN, A. 1992 Efficient program transformations for resilient parallel computation via randomization. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 306 317. The authors show how randomization can be used to automatically transform an arbitrary program written for an ideal parallel machine to run on a completely asynchronous machine, such that the resulting program is work and space efficient relative to the ideal program from which it was derived. Google ScholarDigital Library
KELSEN, P. 1992. On the parallel complexity of computing a maximal independent set in a hypergraph. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 339-350. A maximal independent set in a hypergraph is a subset of vertices that is maximal with respect to the property of not containing any edge of the hypergraph. Kelsen derandomizes the randomized algorithm of Beame to Luby to obtain the first sublinear-~me deterministic algorithm for hypergraphs with edges of size O(1). Google ScholarDigital Library
KILIAN, J. 1992. A note on efficient zeroknowledge proofs and arguments. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 723-732. The standard definition of an interactive proof requires that the verifier accept a correct proof and reject an incorrect assertion with probability at least 2/3. This paper shows how to efficiently reduce the error probability to less than 2 k where k is some easily adjustable security parameter. Google ScholarDigital Library
KILIAN, J. 1990. Uses of Randomness in Algorithms and Protocols. MIT Press, Cambridge, Mass. Kilian's Ph.D. dissertation, which was selected as an ACM Distinguished Dissertation, 1989, is in three parts. The first part describes a randomized algorithm to generate large prime numbers which have short, easily verified certificates of primality. The algorithm provides short, deterministically verifiable proofs of primality for all but a vanishing fraction of prime numbers. The second part considers the secure circuit evaluation problem in which two parties wish to securely compute some function on their private information. Kilian reduces this problem to an oblivious transfer protocol. The third part of the dissertation generalizes probabilistic interactive proof systems to multiple provers. He shows that any language that has a multiprover interactive proof system has a zero-knowledge multiprover interactive proof system. Google ScholarDigital Library
K3LI~, J., M~EALI, S., AND OSTROVSKY, R. 1989. Minimum resource zero-knowledge proof. In Proceedings of the 30th Ann ual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 474-479. The various resources such as number of envelopes, number of oblivious transfers, and total amount of communication required by zero-knowledge !oro~ocols are considered. The paper presents a technique of executing k rounds of a protocol, which guarantees that any polynomial number of NP-theorems can be proved noninteractively in zero knowledge, with the probability of accepting a false theorem below 1/2k. The main result in this paper assumes the existence of trap-door permutations in order to implement the oblivious-transfer protocol.Google Scholar
KLEIN, R. AND LINe:AS, A. 1993. A linear-time randomized algorithm for the bounded Voronoi diagram of a simple polygon. In Proceedings of the 9th Annual ACM Symposium on Computational Geometry. ACM, New York, 124-132. For a polygon P, the bounded Veronoi diagram of P is a partition of P into regions assigned to the vertices of P. Klein and Lingas present a randomized algorithm that builds the bounded Voronoi diagram of a simple polygon in linear expected time. Google ScholarDigital Library
KLrIN, P. N. AND SAm~M, S. 1992. A parallel randomized approximation scheme for shortest paths. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 750-758. A randomized algorithm is given for approximate shortest-path computation in an undirected weighted graph. Google ScholarDigital Library
KLEIN, P. N., STEIN, C., AND T)d~DOS, E. 1990. Leighton-Rao might be practical: Faster approximation algorithms for concurrent flow with uniform capacities. In Proceedings of the 22nd Annual ACM Symposium on the Theory of Computing. ACM, New York, 310- 321. They give an O(m2 log m) expected-time randomized algorithm for approximately solving the concurrent multicommodity flow problem with uniform capacities. Google ScholarDigital Library
KNUTH, D. E. 1973. The Art of Computer Programming. Vol. 3 Sorting and Searching. Addison-Wesley, Reading, Mass. This volume is a repository of sorting and searching algorithms and their analysis. It contains a detailed and thorough treatment of hashing. Google ScholarDigital Library
KNUTH, D. E., MoRms, J. H., AND PRATT, V. R. 1977. Fast pattern matching in strings. SIAM J. Comput. 6, 2, 323-350. This paper presents a fast deterministic algorithm for the problem of determining if a given pattern of m symbols occurs in a text of length n. Their well-known algorithm runs in time O(n + m), making judicious use of a prefix function, which for a given pattern encapsulates knowledge about how the pattern matches against shifts of itself.Google ScholarDigital Library
Ko, K. 1982. Some observations on probabilistic algorithms and NP-Hard problems. Inf. Process. Lett. 14, 1 (Mar.), 39-43. Ko shows that if there is a probabilistic algorithm for an NP- hard problem with a small "two-sided error," then there is a probabilistic algorithm for any NP-complete problem with a small "one-sided error."Google Scholar
KRONSJO, L. 1985. Computational Complexity of Sequential and Parallel Algorithms. John Wiley and Sons, New York. Chapter 8, Section 5.3 addresses probabilistic algorithms. Rabin's algorithms for primality and the nearest-neighbors problem are described. Google ScholarDigital Library
KURTZ, S.A. 1987. A note on random polynomial time. SlAM J. Comput. 16, 5 (Oct./, 852-853. Kurtz shows that P A rh P B ~ BPP with probability 1 for independent random sets A and B. Here, A and B are sets consisting of strings chosen at random, and pA and pB are relativized to A and B, respectively. See Gill {1977{ for additional notation. Google ScholarDigital Library
KUSHILEVITZ, E., MANSOUR, Y., RABIN, M. c., AND ZUCKERMAN, D. 1993. Lower bounds for randomized mutual exclusion. In Proceeding3 of the 25th Annual ACM Symposium on the Theory of Computing. ACM, New York, 154-163. The authors establish a lower bound of l)(log log n) bits on the size of the shared variable required by randomized mutual exclusion algorithms ensuring strong fairness. Slightly weakening the fairness condition results in an exponential reduction in the size of the required shared variable. Google ScholarDigital Library
LAMPORT, L., SHOSTAK, R., AND PEASE, M. 1982. The Byzantine generals problem. ACM Trans Program. Lang SysL 4, 3 (July), 382-401. They proved that Byzantine agreement (the subject of Section 3 5) cannot be reached unless fewer than one-third of the processes are faulty. This result assumes that authentication, i.e., the crypting of messages to make them unforgeable, is not used. With unforgeable messages, they show that the problem is solvable for any n >_ t > 0, where n is the total number of processes and t the number of faulty processes. Google ScholarDigital Library
LEHMANN, D. 1982. On primality tests. SIAM J. Comput. 11, 2 (May). Lehmann presents two algorithms for testing primality based on the extended Riemann hypothesis. The second algorithm is faster than that proposed by Soloway and Strassen {1977} since it does not involve computing the Jacobi symbol.Google ScholarCross Ref
LEHMANN, D. AND RABIN, M. O. 1981. On the advantage of free choice: A symmetric and fully distributed solution to the dining philosophers problem. In Proceedings of the 8th Annual ACM Symposium on the Principles of Programming Languages. ACM, New York, 133-138. A classic paper in the area of randomized distributed algorithms. They show there is no deterministic, deadlock-free, truly distributed and symmetric solution to the dining philosophers problem and describe a simple probabilistic alternative. Google ScholarDigital Library
LEHMER, D.H. 1927. Tests for primality by the converse of Fermat's Theorem. Bull. Am. Math. Soc. 33, 1, 327 340. This paper presents the Lucas-Lehmer heuristic for primality testing.Google ScholarCross Ref
LEIGHTON, F.T. 1992. Methods for message routing on parallel machines. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 77-96. This survey includes the topic of randomized wiring. Google ScholarDigital Library
LEIGHTON, F. T. AND MAGGS, B. M. 1992. Fast algorithms for routing around faults in multibutterfiies and randomly-wired splitter networks. IEEE Trans. Comput. 41, 5 (May), 578-587. This paper describes simple deterministic O(log N)-step algorithms for routing permutations of packets in multlbutterflies and randomly wired splitter networks. The algorithms are robust against faults (even in the worst case) and are efficmnt from a practical point of view. Google ScholarDigital Library
LmGHTON, F. T. AND MAGGS, B ~I. 1989 Expanders might be practical: Fast algor:thms for routing around faults in multlbutterflies. In Proceedzngs of the 30th Annual IEEE Symposium on the Foundations of Computer Sczence. IEEE, New York, 384 389. This paper contains a simpler version of Upfal's {1989} results and algorithms for routing on randomized multibutterflies in the presence of faults.Google Scholar
LEIGHTON, F. T., MAKEnON, F, PLOTKIN, S, STEIN, C., TARDOS,}~., AND TRAGOUDAS, S. 1991. Fast approximation algorithms for multicommodity flow problems. In Proceedtngs of the 23rd Annual ACM Symposzum on the Theory of Computing ACM, New York, 101 111. The paper presents randommed algorithms for approximately solving the multlcommodlty flow problem. The algorithms run in polynomial t~me with high probability. Google ScholarDigital Library
LEIGHTON, F. T., LISINSm, D., AND MAGGS, B. M. 1990. Empirical evaluation of randomly-wired multistage networks. In Proceedings of the 1990 IEEE Internatwnal Conference on Computer Design. IEEE, New York, 380 385. This paper presents simulation results comparing the fault tolerance, delay, and other characteristics of butterflies, dilated butterflies, and randomly wired multibutterflies. Randomly wired multibutterflies perform better by many yardsticks.Google ScholarCross Ref
LEV, G., PIPPENGER, N., AND VALIANT, L. 1981. A fast parallel algorithm for routing in permutation networks. IEEE Trans. Comput. C-30, 2 (Feb.), 93-100. This paper presents deterministic algorithms for routing in permutation networks. The fastest algorithms require global knowledge and l~(log2 N) parallel time.Google ScholarCross Ref
LEWIS, T. G. AND CooK, C. R. 1988. Hashing for dynamic and static internal tables. Computer 21, 1, 45 56. The authors survey the classical hashing function approach to information retrieval and show how general hashmg techmques exchange speed for memory. It is a tutorial paper that covers, among other topics, dynamic and static hash tables, perfect hashing, and minimal perfect hashing. Google ScholarDigital Library
LICHTENSTEIN, D., LINIAL, N., AND SAKS, M. 1987. Imperfect random sources and discrete controlled processes. In Procee&ngs of the 19th Annual ACM Symposmm on the Theory of Computing. ACM, New York, 169-177. Imperfect sources are modeled by discrete control processes where the output string of zeros and ones has been tampered with by a controller who can specify certain bits. Several questions concerning the membership of such a string in a prespecified set L are answered. Google ScholarDigital Library
LINIAL, N., Lov/~sz, L., AND WIGDERSON, A. 1988. Rubber bands, convex embeddings, and graph connectivity. Combinatorica 8, 1, 91-102. Several probabilistic algorithms for connectivity computation, both of the Monte Carlo and Las Vegas variety, are given, as is a formalization of the connectivity problem in terms of embedded graphs. Efficient parallel implementations are included. This paper first appeared under the title "A Physical Interpretation of Graph Connectivity and its Algorithmic Applications" in Proceedings of the 27th Annual IEEE Symposium on the Foundations of Computer Science, 1986, pp. 39-53.Google ScholarCross Ref
LIN, J.-H. AND VITTER, J. S. 1992. e-approximations with minimum packing constraint violation. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 771-782. Efficient randomized and deterministic algorithms are presented for transforming optimal solutions for a type of relaxed integer linear program into provably good approximate solutions for the corresponding NP-hard discrete optimization problem. Google ScholarDigital Library
Lovasz, L. 1979. On determinants, matchings and random algorithms. In Fundamentals of Computing Theory. Akademia-Verlag, Berlin. L6v~sz describes a probabilistic method for determining the perfect matching in a simple graph, if one exists, using Tutte's theorem.Google Scholar
LUND, C., FORTNOW, L., KARLOFF, H., AND NISAN, N. 1990. Algebraic methods for interactive proof systems. In Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 2-10. The authors present a new algebraic technique for constructing IP systems and prove that every language in the polynomial-time hierarchy has an interactive proof system. This is a key paper for proving IP = PSPACE {Shamir 1992} and MIP = NEXP {Babai et al. 1990}.Google ScholarDigital Library
LUTZ, J. 1992. On independent random oracles. Theoret. Comput. Sci. 92, 2, 301 307. This paper shows that for every random language A ~ B, P(A) A P(B) - BPP, where P(A) and P(B) are the class of languages in polynomial time relativized to A and B. This improves on the results of Kurtz {1987}. Google ScholarDigital Library
LUTZ, J. AND SCHMIDT, W. 1993. Circuit size relative to pseudo-random oracles. Theoret. Comput. Sc~. 107, 1, 95-120. Assuming pseudorandom oracles, circuit size complexity is compared with deterministic and nondeterministic complexity. The paper also shows that for every p-space random oracle A and almost every oracle A in EPSPACE, NPA is not contained in SIZEA(2~n) for any real a < 1/3, and EA is not contained in SIZEA(2"/n). Google ScholarDigital Library
MAFFIOLI, F., SPERANZA, M. G., AND VERCELLIS, C. 1985. Randomized algorithms. In Combinatorial Optimization--Annotated Bibliography. Wiley Interscience, New York, 89 105. This is a useful annotated bibliography on randomized algorithms.Google Scholar
MAGGS, B. M. AND SITARAMAN, R.K. 1992. Simple algorithms for routing on butterfly networks with bounded queues. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 150-161. The authors present a simple, but nonpure, algorithm for routing a random problem on a fully loaded N-input butterfly with bounded-size ueues in O(log N) steps, with high probability. Google ScholarDigital Library
MAJEWSK~, B. S., WORMALD, N. C, HAVAS, G., AND CZECH, Z.J. 1993. Graphs, hypergraphs and hashing. In Proceedings of the 19th Internatwnal Workshop on Graph-Theoretic Concepts ~n Computer Science (WG'93). The authors generalize the method presented in Czech et al. {1992} by mapping the input set into a hypergraph rather than a graph. This modification allows a reduction in the size of the program, while maintaining all other features of the method. Also, the hash function generation time is reduced.Google Scholar
MANBER, U. AND TOM?A, M. 1985. Probabilistic, ondeterministic and alternating decision rees. J. ACM 32, 3 (July), 720-732. This paper ompares lower bounds on the running times of lgorithms that allow probabilistic, nondeterinistic, and alternating control on decision rees. Decision trees that allow internal ranomization at the expense of a small proability of error are shown to run no faster symptotically than ordinary decision trees for collection of problems. An earlier version of his publication appeared in Proceedings of the 4th Annual ACM Symposium on the Theory of omputing, 1982, pp. 234-244. Google ScholarDigital Library
MANsouR, Y., NISAN, N., AND TIWAm, P. 1993. The omputational complexity of universal hashing. heoret. Comput. Sci. 107, 1, 121-133. They rove that any implementation of universal ashing from n-bit strings to m-bit strings equires a time-space tradeoff of TS = fl(nm). Google ScholarDigital Library
MATIAS, Y. 1993. Highly parallel randomized lgorithms. In Proceedings of the 3rd ACM orkshop on Parallel Algorithms. ACM, New ork. Matias surveys highly efficient ranomized parallel algorithms including: nearly onstant-time algorithms for hashing, dictioary implementation, approximate compaction, pproximate sum, and automatic processor cheduling in parallel algorithms.Google Scholar
MATIAS, Y. AND VISHKIN, U. 1991. Converting igh probability into nearly constant timeith applications to parallel hashing. In Proeedings of the 23rd Annual ACM Symposium n the Theo~p/ of Computing'. ACM, New York, 07 316. Randomized parallel algorithms are iven for constructing a perfect hash function n expected polylogarithmic time and for generting a random permutation in polylogarithmic ime. Google ScholarDigital Library
MATIAS, Y., VITTER, J. S., AND NI, W.-C. 1993. ynamic generation of discrete random varibles. In Proceedings of the 4th Annual ACM- IAM Sympostum on Discrete Algorithms. CM, New York, 361-370. Efficient randomzed algorithms are given to generate a random ariate distributed according to a dynamic et of weights. The base version of each algoithm generates the discrete random variate in (log*N) expected time and updates a weight n 0(2l~g~N) expected time in the worst case. t is shown how to reduce the update time to (log* N) amortized expected time. Google ScholarDigital Library
MATOU~EK, J., MOUNT, D. M., AND NETANYAHU, N. S. 993. Efficient randomized algorithms for the repeated median line estimator. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 74-82 Computing a statistical estimator can be viewed as the problem of fitting a straight line to a collection of n points in the plane. The breakdown point of an estimator is the fraction of outlying data points (up to 50%) that may cause the estimator to take on an arbitrarily large aberrant value. The authors present a (not~so simple) O(n log n) randomized expected-time algorithm for the problem of computing a 50% breakdown point estimator, namely, the Siegel, or repeated-median, estimator. A simpler O(n logs n) randomized algorithm for the problem is also given, which the authors contend actually has O(n log n) expected time for "many realistic input distributions." Google ScholarDigital Library
MCKAY, B. AND WORMALD, N. 1990. Uniform genration of random graphs of moderate degree. . Alg. 11, 1, 52-67. A randomized algorithm is iven for generating k-regular graphs on n ertices, uniformly at random. The expected unning time of the algorithm is O(nk3) for = O(nl/3). Special cases, such as bipartite raphs with given degree sequences, are conidered. Google ScholarDigital Library
MEGIDDO, N. AND ZEMEL, E. 1986. An O(n log n) andomizing algorithm for the weighted uclidean 1-center problem. J. Alg. 7, 3 (Sept.), 58-368. A set of points p, - (x, y~) and their eights w, I < z _< n, are given. It is required o find a point p that minimizes the maxium first moment of the weights of the p~, i.e, he p tha6 minimizes t-I(p) AXi~_<nW~ d(p,p~) where d(p,p~) is the agnitude of the distance between p and p,. A andomized algorithm that does this with a mall probability of error is presented.Google Scholar
MEHLHORN, K. 1984a. Data Structures and Algoithms 1: Sorting and Searching. EATCS onographs on Theoretical Computer Science, ol. 1. Springer-Vertag, New York. Volume 1 of his three-volume series is an excellent source or searching and sorting algorithms. It conains sections on quicksort (Section II.1.3), perect hashing (Section III.2.3), and universal ashing (Section 1II.2.3). Google ScholarDigital Library
MEHLHORN, K. 1984b. Graph Algorzthms and P-Completeness. EATCS Monographs on Theretical Computer Science, vol. 2. Springererlag, New York. Section IV. 9.2 gives a robabilistic algorithm for graph connectivity, nd Section VI.8 deals, in part, with primality esting. Google ScholarDigital Library
MEHLHORN, K. 1984c. Multi-Dimenstonal earchtng and Computational Geometry. ATCS Monographs on Theoretical Computer cience, vol. 3. Springer-Verlag, New York. This ook is the last of three volumes. Chapter 7 is evoted to multidimensional data structures nd Chapter 8 to problems in computational eometry. Google ScholarDigital Library
MEHLHORN, K. 1982. On the program size of perect and universal hash functions. In Proceedngs of the 23rd Annual IEEE Symposium on he Foundations of Computer Science. IEEE. ew York, 170-175. A must for readers intersted in perfect hashing. It proves that for n istinct keys from {0.. N - 1}, there exists a rime number p = O(n21n(N)) such that for ny two keys x, and x j, x~(mod p) ~ xj(mod p). urther, a good deterministic algorithm exists or finding p; it can be determined even more fficiently using a randomized algorithm. Sevral other results concerning the construction nd length of perfect and universal hashing unctions are proved.Google Scholar
MEHLHORN, K. AND SCHMIDT, E. 1982. Las Vegas s better than determinism in VLSI and disributed computing. In Proceedings of the 4th Annual ACM Symposium on the Theory f Computing'. ACM, New York, 330-337. his paper demonstrates a problem where the heoretical lower bounds for distributed deterinistic solutions can be improved using andomness. Let X= (x1,x2 .. ,xn), Y- Yi, Y2,.., Yn), be stored on two different sites, here x~ and y~ are integers between 0 and '~ - 1. The function f(X, Y)--which is defined o be I if there exists an t such that x, = y,, nd 0 otherwise--is to be computed with minium communication. This problem requires n2 essage bits in the deterministic case, but an (n log n log n) average running-time probailistic algorithm is demonstrated. Google ScholarDigital Library
MEYER AUF DER HEIDE, F. 1990. Dynamic hashng ~t~atoffiog. In Pnoeoodin~'~ of the 15th Symosium on the Mathematical Foundations of omputer Science. Lecture Notes in Computer cience, vol. 452. Springer-Verlag, New York, 6-87. This paper contains a survey of dynaic hashing techniques. It evaluates hashing lgorithms with respect to probability of colliions, bucket sizes, evaluation time, and the ime needed to construct a hash function. Parllel, distributed, and sequential algorithms are onsidered. Google ScholarDigital Library
MEYER AUF DER HEIDE, F. 1985. Simulating robabilistic by determining algebraic compuation trees. Theoret. Comput. Sct. 41, 2/3, 25-330. This paper overlaps with the paper Nondeterministic Versus Probabilistic Linear earch Algorithms," Proceedings of the 26th nnual IEEE Symposium on the Foundations f Computer Science, 1985, pp. 65-73. It is hown that nondeterministic algorithms are ess complex than their probabilistic counterarts even when the probabilistic choices are ssigned zero cost and error is allowed in all omputations. The specific algorithms considred are linear search algorithms. Google ScholarDigital Library
MIGNOTTE, M. 1980. Tests de primalite. Theoret. omput. Sci. 12, 1, 109-117. In French. Sureys the field of primality testing from a comutational complexity perspective.Google Scholar
MILLER, G. L. 1976. Reimann's hypothesis and est for primality. J. Comput. Syst. Sci. 13, 3, 00-317. A seminal paper in the development f primality-testing algorithms. It presents two lgorithms for primality testing. The first one uns in O(n1/7) time. The second one, which is ctually a polynomial-time algorithm O(log4 n)/, assumes the Extended Riemann ypothesis. This paper, which first appeared in roceedings of the 7th Annual ACM Sympoium on the Theory of Computing, 1975, pp. 34-239, also proves that a certain class of unctions is computationally equivalent to facoring integers. Google ScholarDigital Library
MILLER, G. L. AND REIF, J.H. 1991. Parallel tree ontraction, Part 2: Further applications. SIAM . Comput. 20, 6 (Dec.), 1128 1147. In this ollowup of Miller and Reif {1989}, the authors resent many applications of their parallel tree ontraction technique, including algorithms for ubexpression evaluation, tree and graph isoorphism, and building canonical forms of rees and planar graphs. Google ScholarDigital Library
MILLEg, G. L. AND REIF, J.H. 1989. Parallel tree ontraction, Part 1: Fundamentals. In Advanes in Computing Research 5: Randomness and omputation. JAI Press, Greenwich, Conn. hey exhibit a randomized parallel algorithm or subtree isomorphism that uses O(log n) ime and O(n/log n) processors. This was the irst polylog parallel algorithm for the problem. ee also the related paper "Parallel Tree Conraction and Its Applications," in Proceedings f the 26th Annual IEEE Symposium on the oundations of Computer Science, 1985, pp. 78-489, and the companion paper {Miller and eif 1991}.Google Scholar
MITRA, D. AND CIESLAK, R.A. 1987. Randomized arallel communication on an extension of he Omega network. J. ACM 34, 4, 802-824. his is an extension of Valiant and Aleluinas' lgorithm to eliminate the need for schedulng. This algorithm also works on networks of ixed-degree nodes. Google ScholarDigital Library
MONIER, L. 1980. Evaluation and comparison of wo efficient probabilistic primality testing lgorithms. Theoret. Comput. Sc~. 12, 1, 97 108. onier presents an interesting comparison of he Miller-Rabin {Rabin 1976} and olovay-Strassen {1977} primality-testing lgorithms, showing that the former is always ore efficient than the latter. In the process, e proves that at least 3/4 of the numbers in he set (1,2,..,n- 1} are witnesses to the ompositeness of n, for n composite. This trengthens the bound given in Rabin {1976}.Google ScholarCross Ref
MOTWANI, R., NAOR, J., ANn NAOR, M. 1989. The robabilistic method yields deterministic paralel algorithms. In Proceedings of the 30th nnual IEEE Symposium on the Foundations f Computer Science. IEEE, New York, 8 3. This paper presents a method of conerting randomized parallel algorithms into eterministic parallel (NC) algorithms. Their pproach is based on a parallel implementation f the method of conditional probabilities due o Spencer {1994}, which was originally introuced with the aim of converting probabilistic roofs of existence of combinatorial structures nto deterministic algorithms that can actually onstruct these structures. Restrictions on the echnique to a certain class of randomized NC lgorithms are discussed. Google ScholarDigital Library
MULMULEY, K. 1994. Computational Geometry: n Introduction through Randomtzed Algoithms. Prentice-Hall, Englewood Cliffs, N.J. his book presents a number of randomized lgorithms for problems in computational gemetry. It is meant to serve as an introduction o computational geometry; the author chooses andomized algorithms to do the job since they re usually simpler to understand than their eterminisic counterparts. The book is divided into wo parts: basics and applications. Applicaion areas considered include arrangements f hyperplanes, convex polytopes, range earch, and computer graphics. A chapter on erandomization is also given.Google Scholar
MULMULEY, K. 1992. Randomized geometric lgorithms and pseudo-random generators. In roceedings of the 33rd Annual IEEE Sympoium on the Foundattons of Computer Science. EEE, New York, 90-100. This paper shows hat a generalization of the familiar linear conruential pseudorandom generator that uses (log n) bits can be substituted for the random ource in many randomized incremental algoithms used in computational geometry withut affecting the order of complexity of the xpected running time, thereby reducing he number of truly random bits needed.Google Scholar
MULMULEY, K., VAZIRANI, U. V., AND VAZIRANI, V. V. 987. Matching is as easy as matrix inversion. Combinatoriea 7, 1, 105 113. An elegant parallel, randomized algorithm for finding a p~rfoct matching in a ~implo graph ba~ed on Tutte's matrix is presented. The algorithm, which is made possible by a probabilistic lemma called the isolation lemma, requires inversion of a single integer matrix which can be parallelized. Google ScholarDigital Library
MUTHUKRISHNAN, S. 1993. Detecting false atches in string matching algorithms. In Proeedings of the 4th Internatwnal Conference n Combinatorial Pattern Matching. Lecture otes in Computer Science, vol. 684. Springer~ erlag, New York, 164-178. The Karp and abin 1987 randomized string-matching algoithm may report, with a small probability, a alse match. Muthukrishnan presents a paralel algorithm to detect the existence of such a alse match. His algorithm runs in O(1) time nd uses O(n) CRCW PRAM processors, where is the length of the input text, and can e used to efficiently convert the Monte Carloype string-matching algorithm of Karp nd Rabin into a Las Vegas-type algorithm. uthukrishnan also considers the problem of etecting all false matches. Google ScholarDigital Library
NAOR, J. AND NAOR, M. 1990. Small-bias proability spaces: Efficient constructions and pplications. In Proceedings of the 22nd Annual CM Symposium on the Theory of Compuing. ACM, New York, 213 223. This paper hows an efficient construction of a small probbility space on n binary random variables uch that for every subset its parity is either ero or one with "almost" equal probability. pplications are shown in problems such as the erandomization of algorithms and reducing he number of random bits required by certain andomized algorithms. Google ScholarDigital Library
NAOR, M. AND STOCKMEYER, L. 1993. What can e computed locally In Proceedings of the 25th nnual ACM Symposium on the Theory of omputing. ACM, New York, 184 193. In the ontext of a distributed network, Naor and tockmeyer investigate Locally Checkable abelmg (LCL) problems, where the legality f a labeling (e.g., coloring) can be checked ocally, i.e., within time (or distance) indepenent of the size of the network. Among their esults they show that randomization cannot ake an LCL problem local, i.e, if a problem as a local randomized algorithm then it has a ocal deterministic algorithm. Google ScholarDigital Library
NATARA.JAN, B. K. 1992. Probably approximate earning over classes of distributions. SIAM J. omput. 21, 3 (June), 438 449. Natarajan genralizes the model of probably approximate earning proposed by Valiant {1984b}. Google ScholarDigital Library
NATIONAL RESEARCH COUNCIL. 1992 Probability nd Algortthms. National Academy Press, ashington, D.C. This book ~s an outgrowth of panel on Probabfiity and Algorithms assemled by the National Research Council in 1991. he panel was charged with writing a survey n probabilistic algorithms and on the probabilistic analysis of conventional algorithms. he result is a collection of 12 indepenent, yet somewhat complementary, articles on he following topics: simulated annealing D. Bertsimas and J. Tsitsiklis); approximate ounting via Markov chains (D. Aldous); proabilistic (BPP) algorithms for speedup J. Feigenbaum and J. C. Lagarias); cryptograhy and authentication (J. Feigenbaum); eneration of pseudorandom numbers (J. C. agarias); probabilistic analysis of packing and elated problems (E. G. Coffman, Jr., D.S. ohnson, P. W. Shor, and G. S. Lueker); probems in Euclidean combinatorial optimization J. M. Steele); probabilistic analysis in linear rogramming (R. Shamir); randomized parallel lgorithms (V. Ramachandran); randomly ired multistage networks (B. M. Maggs); and erandomization (J. M. Steele).Google Scholar
NISAN, N. 1993. On read-once vs. multiple access o randomness in logspace. Theoret. Comput. ci. 107, 1, 135-144. This paper shows that very language accepted with bounded twoided error by a read-once randomized logspace achine can be accepted with zero error by a andomized logspace machine with multiple ccess to the random bits. Also, the class of anguages accepted with two-sided error by a andomized logspace machine with multiple ccess to the random bits is shown to be the lass of languages that are in logspace relative o almost every oracle. Google ScholarDigital Library
NISAN, N. AND ZUCKERMAN, D. 1993. More deterinistic simulation in logspace. In Proceedings f the 25th Annual ACM Symposium on he Theory of Computtng. ACM, New York, 35 244. It is shown that any randomized pace(S) algorithm that uses only poly(S) ranom bits can be simulated deterministically in pace(S), for S(n) >_ log n. Google ScholarDigital Library
OREN, Y. 1987. On the cunning power of cheatng verifiers: Some observations about zero nowledge proofs. In Proceedings of the 28th nnual IEEE Symposium on the Foundations f Computer Science. IEEE, New York, 462- 71. Oren differentiates between aux~liarynput zero knowledge and blackbox stmulation ero knowledge. He shows that all known zeronowledge proofs are in the latter category. dditionally, it is proved that blackbox sire ulazon zero knowledge implies auxiliary input nowledge and that the latter corresponds o the original defimtion given in Goldwasser t al. {1989}.Google Scholar
PACHL, J. 1987. A lower bound for probabilistic istributed algorithms. J. Alg. 8, 1, 53-65. The inimum number of messages required to ind the extremal value of node ids in an synchronous network deterministically is H)(n log n). This paper shows that this bound olds even for probabilistic algorithms. Google ScholarDigital Library
PAZ, A. 1971. Introduction to Probabilistic utomata. Academic Press, New York. Paz evelops a theory of equivalence among robabilistic automata. Google ScholarDigital Library
PEASE, M., SHOSTAK, R., AND LAMPORT, L. 1980. eaching agreement in the presence of faults. . ACM 27, 2, 228-234. This paper is similar to heir 1982 publication Lamport et al. {1982}, ut contains a rigorous proof of the impossibilty of Byzantine agreement for the case n = 3, ~ 1. As usual, n is the total number of proesses, and t is the number of faulty processes. Google ScholarDigital Library
PELLECmM, M. 1993. On line missing polyhedral ets in 3-space. In Proceedings of the 9th nnual ACM Symposium on Computational eometry. ACM, New York, 19-28. Pellegrini ives an O(n15+~) randomized expected-time lgorithm that tests the separatton property: oes there exist a direction v along which a set f n red lines can be translated away from a et of n blue lines without collisions? Google ScholarDigital Library
PERRY, K. 1985. Randomized Byzantine agreeent. IEEE Trans. Softw. Eng. SE-11, 6 (June), 39-546. Perry presents randomized algoithms for Byzantine agreement that, like the lgorithm of Rabin {1983}, terminate in an xpected number of rounds which is a small onstant independent of n and t. As usual, n is he total number of processes, and t is the umber of faulty processes. However, Perry's lgorithm can tolerate a greater number of aulty processes. He requires only n >_ 6t + 1 n the asynchronous case and n >_ 3t + i in the ynchronous case.Google Scholar
PETERSON, G. L. 1982. An O(n log n) unidirecional algorithm for the circular extrema probem. ACM Trans. Program. Lang. Syst. 4, 4 Oct.), 758-762. Peterson presents a deterinistic distributed algorithm for finding the argest of a set of n uniquely numbered proesses in a ring. The algorithm requires O(n og n) messages in the worst case and is uniirectional. The number of processes is not nitially known. Google ScholarDigital Library
PRATT, V. R. 1975. Every prime has a succinct ertificate. SIAM J. Comput. 4, 3, 214 220. his paper proves, using the Lucas-Lehmer euristic for testing primeness, that just ike composite numbers, the primeness of a rime number n can be demonstrated by an (log n)-long proof.Google ScholarCross Ref
PUGH, W. 1990. Skip lists: A probabilistic alterative to balanced trees. Commun. ACM 33, 6 June), 668-676. This paper presents skip lists, ists in which a node may have a pointer to a ode some number of places ahead on the list. uch pointers, called "forward pointers," thereore "skip" over intermediate nodes. A node ith k forward pointers is said to be a level-k ode. Skip lists are probabilistic in that the evel of a node is chosen randomly with he property that a node's tth forward pointer oints to the next node of level, or higher. It is hown that skips lists can efficiently impleent abstract data types such as dictionaries nd ordered lists in that the expected time to earch for an item is O(log n). Google ScholarDigital Library
RABIN, M.O. 1983. Randomized Byzantine Genrals. In Proceedings of the 24th Annual IEEE ymposium on the Foundations of Computer cience. IEEE, New York, 403-409. Rabin preents a randomized algorithm for asynchronous yzantine agreement that terminates in a contant expected number of rounds. Cryptograhy is used to simulate a trusted dealer that istributes random coin tosses before the start f the algorithm. Rabin's algorithm works only f less than one-tenth of all processes are faulty.Google ScholarDigital Library
RABIN, M. O. 1980a. A probabilistic algorithm or testing primality. J. Num. Theor. 12, 1, 28-138. Rabin's paper introduces another celbrated algorithm for fast, randomized primalty testing. This paper is based on a different umber-theoretic property than that used by olovay and Strassen {1977}.Google Scholar
RABIN, M. O. 1980b. Probabilistic algorithms in inite fields. SIAM J. Comput. 9, 2 (May), 73 280. Rabin presents probabilistic algoithms for finding an irreducible polynomial f degree n over a finite field, the roots of polynomial, and the irreducible factors f a polynomial.Google ScholarCross Ref
RABIN, M. O. 1976. Probabilistic algorithms. In lgorithms and Complexity: New Directions nd Recent Results. Academic Press, New York, 1 39. This classic paper on probabilistic algoithms features algorithms for primality testng and nearest neighbors.Google Scholar
RAB~N, M. O. 1963. Probabilistic automata. Inf. ontr. 6, 3, 230-245. This is a seminal paper n the theory of probabilistic automata. Rabin efined the notion of a language being accepted y a probabilistic automaton relative to a cutoint lambda. One of his key results was to how that there exist finite-state probabilistic utomata that define nonregular languages.Google Scholar
RABIN, M. AND VAZIRANI, V. 1989. Maximum matchings in general graphs through randomization. J. Alg. 10, 4, 557 567. This paper presents a conceptually simple algorithm for maximal matching in a graph of n nodes with complexity O(M(n)n loglog n)~ where M(n) is the number of operations needed to multiply two n x n matrices. Google ScholarDigital Library
RAGHAVAN, P. 1990. Lecture notes on randomized algorithms. Res. Rep. RC 15340 (#68237), IBM T. J. Watson Research Center, Yorktown Heights, N.Y. This report consists of lecture notes from a course taught by the author. These notes give a thorough introduction to many randomized algorithms in computational geometry, graph theory, VLSI, and networks. The basic mathematical background essential for understanding these algorithms is presented in detail.Google Scholar
RAGHAVAN, P. 1988. Probabilistic construction of deterministic algorithms: Approximating packing integer problems. J. Comput. Syst. Sc,. 37, 130 143. Based on the derandomization technique of conditional probabilities, Raghavan develops a methodology for converting the probabilistic existence proof of a near-optimum integer solution to an integer program into a deterministic approximation algorithm. Google ScholarDigital Library
RAJASEKARAN, S. 1991. Randomized algorithms for packet routing on the mesh. Tech. Rep. M-CIS-91-92, Dept. of Computer and Information Sciences, Univ. of Pennsylvania, Philadelphia. Efficient randomized algorithms for store and forward, multipacket, and cut through routing of packets on a mesh-connected computer are surveyed. The expected running times and queuing complexity of these algorithms are analyzed.Google Scholar
RAJASEKAatN, S. AND REIP, J.H. 1989. Optimal and sublogarithmic time randomized parallel sorting algorithm. SIAM J. Comput. 18, 3 (June), 594-607. This paper presents an optimal, randomized, parallel algorithm for sorting n numbers in the range {1.. n} on a parallel random-access machine that allows both concurrent reads and concurrent writes of a global memory. Google ScholarDigital Library
RAMAKRISHNA, M. V AND PORTICE, G. A. 1991. Perfect hashing functions for hardware applications. In Proceedings of the 7th International Conference on Data Engineering. IEEE, New York. A hardware scheme for constructing an associative memory using a perfect hash function is described. A simple trial-and-error scheme is used to find a perfect hash function. Google ScholarDigital Library
RAMEStt, H. 1993. On traversing layered gTaphs on-line. In Proceedings of the 4th Annual ACM-SIAM Symposium on D~screte Algortthms. ACM, New York, 412-421. A layered graph is a connected weighted graph whose vertices are partitioned into sets (i.e., layers) Lo, L1, L2,.., and all edges connect vertices in consecutive layers. Ramesh presents a randomized on-line algorithm for traversing wldth-w layered graphs with a competitive ratio of O(w~5). His algorithm represents the first polynomially competitive randomized algorithm for layered-graph traversal. Google ScholarDigital Library
RE1F, J. H. 1985. Optimal parallel algorithms for integer sorting and graph connectivity. In Proceedings of the 26th Annual IEEE Symposium on the Foundations of Computer Sctence. IEEE, New York. This paper contains some results on the use of randomization in parallel algorithms.Google Scholar
REIF, J. H. AND SEN, S. 1992. Optimal parallel randomized algorithms for three-dimensional convex hulls and related problems. SIAM J. Comput. 21, 3 (June), 466 485. An optimal, parallel, randomized algorithm for computing the intersection of half-spaces in 3D is given. The algorithm provides efficient solution techniques for convex hulls in 3D and Vornol diagrams of point sites on a plane. An earlier version of the paper appeared as "Polling: A New Random Sampling Technique for Computational Geometry," in Proceedzngs of the 21st Annual ACM Symposium on the Theory of Computing, 1989, pp. 394 404. Google ScholarDigital Library
REIF, J. H. AND SPIRAKIS, P. G. 1984. Real time sychronization of interprocess communication. ACM Trans. Program. Lang. Syst. 6, 2, 215-238. They present probabilistic distributed algorithms for the guard-scheduling problem (Section 3.2) that guarantee real-time response. A preliminary version of this paper appeared as "Distributed Algorithms for Synchronizing Interprocess Communication in Real Time," in Proceedings of the 13th Annual ACM Symposium on the Theory of Computing, 1981. Google ScholarDigital Library
REISCHUK, R. 1985. Probabilistic parallel algorithms for sorting and selection. SIAM J. Cornput. 14, 2 (May), 396 409. This paper considers the problems of selecting the k smallest elements out of a set of n keys and sorting the n keys using n processors in parallel. Re~schuk showed that the former can be done in constant time with probability 1 - 2 cnll~81 and the latter in O(log n) time. Both algorithms meet the corresponding information-theoretic lower bounds in terms of processor time product as well as the optimal speedup attainable using n processors. An earlier version appeared as Reischuk { 1981}.Google ScholarCross Ref
REISCHUK, R. 1981. A fast probabilistic parallel sorting algorithm. In Proceedings of the 22nd Annual IEEE Symposzum on the Foundations of Computer Science. IEEE, New York, 212 219. Reischuk considers the problems of selecting k smallest elements out of a set of n keys and sorting the n elements using n processors in parallel. He shows that the former can be done m constant time with probability i- 2 ~n~Js~ and the latter in O(log n) time. This achieves the information-theoretic lower bound in terms of processor time product as well as the optimal speedup attainable using n processors.Google Scholar
R~EST, R. L., SHAMIR, A., AND ADLEMAN, L. 1978. A method for obtaining digital signatures and public key cryptosystems. Commun. ACM 21, 2 (Feb.), 120. The basics of trap-door functions and the famous RSA public-key cryptosystem are presented in this paper. Google ScholarDigital Library
RUBINSTEIN, R. Y. 1981. Simulation and the Monte Carlo Method. John Wiley and Sons, New York. This work is an indepth look at the use of random sampling (the Monte Carlo method) in the context of simulation and numerical integration. Google ScholarDigital Library
SALOMAA, A. 1969. Theory of Automata. Pergamon Press, New York. Chapter 2 of this book discusses probabilistic automata and develops a general theory of stochastic languages.Google Scholar
SANTHA, M. AND VAZIRANI, U.V. 1986. Generating quasi-random sequences from semi-random sources. J. Comput. Syst Scl. 33, 1 (Apr.), 75-87. The authors introduce the notion of semirandom sources where the next bit of the output is produced by an adversary by the flip of a coin of variable bias. The adversary can look at the previously output bits and use them to set the bias in the coin. The bias, which helps model correlation among bits, is constrained to be between two limits. Google ScholarDigital Library
SCHMIDT, J. P. AUD SIEGEL, A. 1990. The spatial complexity of oblivious k-probe hash functions. SIAM J. Comput. 19, 5, 775-786. This paper gives, among other results, a lower bound for the average space required by programs for oblivious k-probe hash functions. A probabilistic construction of a family of oblivious k-probe hash functions that nearly match this bound is also given. Google ScholarDigital Library
SCHMIDT, J. P., SIEGEL, A., AND SRINIVASAN, A. 1993. Chernoff-Hoeffding bounds for applications with limited independence. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 331-340. Chernoff-Hoeffding bounds are frequently used in the design and analysis of randomized algorithms to bound the tail probabilities of the sums of bounded and independent random variables. The authors give a simple technique which gives slightly better bounds than these and which requires only limited independence among the random variables. Google ScholarDigital Library
SCHNEIDER, F. B. 1982. Synchronization in distributed programs. ACM Trans. Program. Lang. Syst. 4, 2 (Apr.). Schneider presents a timestamp-based distributed algorithm for CSP output guards. A probabilistic algorithm for output guards is described in Section 3.2. Google ScholarDigital Library
SCHONHAGE, h. 1988. Probabilistic computation of integer polynomial GCDs. J. Alg. 9, 3 (Sept.), 365-371. The GCD of two univariate integer polynomials of degree < n, with their l1 norms bounded by 2r', is shown to be reducible to GCD computation for long integers. A probabilistic approach yields an expected complexity of O(n(n + h)1. o{1~) bit operations. Google ScholarDigital Library
SCHROEDER, M.R. 1984. Number Theory in Science and Communication with Applications in Cryptography, Physics, Biology, Digital Informatron and Computing. Springer-Verlag, New York. Schroeder presents intuitive discussions on prime numbers, their distribution, fractions, congruences, etc. Several applications of number theory in such diverse fields as cryptography and Fraunhofer diffraction are discussed. A good source of basic number theory results for algorithm deaigners. Google ScholarDigital Library
SCHWARTZ, J. T. 1979. Probabilistic algorithms for verification of polynomial identities. In ISSAC 79: Proceedings of the Internatwnal Symposium on Symbolic and Algebraic Computation. Lecture Notes in Computer Science, vol. 72. Springer-Verlag, New York. This paper, whieh also appeared in J. ACM 27, 4 (Oct. 1~80), pp. 701 717, presents probabilistic methods for testing polynomial identities and properties of systems of polynomials. Google ScholarDigital Library
SCHWARTZ, J. 1978. Distributed synchronization of communicating sequential processes. Tech. Rep., DAI Res. Rep. 56, Univ. of Edinburgh, U.K. Schwartz presents a distributed algorithm for CSP output guards based on priority ordering of processes. A probabilistic algorithm for output guards is described in Section 3.2.Google Scholar
SCHWARZKOPF, O. 1991. Dynamic maintenance of geometric structures made easy. In Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 180-196. Schwarzkopf presents a randomized algorithm for maintaining Convex Hulls with m points that runs in expected time O(log m) per update for dimensions 2 and 3, O(mlogm) for dimensions 4 and 5, and O(mtJ/2j t) for dimensions greater than 5. Google ScholarDigital Library
SEIDEL, R. 1991. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons. Comput. Geom. Theor. Appl. 1, 1, 51 64. Seidel's randomized algorithm runs in O(n log*n) expected time and is simpler than the deterministic O(n) algorithm due to B. Chazelle. Google ScholarDigital Library
SUALLIT, J. 1992. Randomized algorithms in "primitive cultures." SIGACT News 23, 4, 77- 80. Shallit, in a slightly tongue-in-cheek manner, traces back some of the concepts of randomized algorithms to the native American society of the Naskapi and the Central African society of the Azande. Roots in the works of Pierre Laplace and Lord Kelvin are also pointed out. Google ScholarDigital Library
SnAreR, A. 1992. IP = PSPACE. J. ACM 39, 4. This paper shows that the set of problems for which interactive protocols exist is precisely the set of problems which are solvable within polynomial space on a Turing machine. Google ScholarDigital Library
SHout, V. 1993. Fast construction of irreducible polynomials over finite fields. In Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 484-492. A randomized algorithm is presented that constructs an irreducible polynomial of given degree n over a finite field Fq. It uses an expected number of O~ (n2+ n log q) operations in Fq, where the "soft-O' O - indicates an implicit factor of (log n )o(1). Google ScholarDigital Library
SIEGEL, A. 1989. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In Proceedings of the 30th Annual IEEE Symposium on the Foundotions of Computer Science. IEEE, New York, 20-25. An algorithm for constructing log n-wise independent hash functions that can be evaluated in constant time is presented.Google ScholarDigital Library
SIPSER, M. 1988. Expanders, randomness, or time versus space. J. Cornput. Syst. Sci_ 36~ 3. 379-383. Contains a discussion on efficiently reducing the probability of error in randomized algorithms. It also describes a relationship between pseudorandomness, time, and space used by certain algorithms if certain types of expander graphs can be explicitly constructed. Google ScholarDigital Library
SMITH, J. 1983. Public key cryptography. Byte 8, 1 (Jan.), 198-218. This is a simple exposition of public-key cryptography.Google Scholar
SOLOVAY, R. AND STRASSEN, V. 1978. Erratum: A fast Monte-Carlo test for primality. SIAM J. Comput. 7, I (Feb.). A minor correction in the analysis presented in Solovay and Strassen{1977} is reported by the authors. The basic results of the earlier work, however, still hold.Google ScholarCross Ref
SOLcVAY, R. AND STRASSEN, V. 1977. A fast VIonte-Carlo test for primality. SIAM J. Cornput. 6, 1 (Mar.), 84-85. Another test for primality based on the abundance of witnesses to compositeness of n is presented. The test entails picking a random number a (1 _< a < n) and computing ~ = a(n-~)/2(mod n), where -1< ~<n-2. If the Jacobi symbol 8 = (a/n) equals e then n is prime; else, if either gcd(a, n) > i or S ~= ~, decide n to be composite. The second decision has less than 1/2 probability of being wrong.Google Scholar
SPENCER, J. 1994. Ten Lectures on the Probabilistic Method. 2nd ed. CBMS-NSF Regional Conference Series in Mathematics. SIAM, Philadelphia, Pa. Spencer presents a method of converting probabilistic proofs of existence of certain combinatorial structures into deterministic algorithms that construct these structures.Google Scholar
SPmAKIS, P. G. 1982. Probabilistic algorithms, algorithms with random inputs and random combinatorial structures. Ph.D. thesis (UMI Order Number DA 8216206), Harvard Univ., Cambridge, Mass. This thesis puts forth a new model, Random Independence Systems, for the probabilistic analysis of deterministic algorithms with random inputs, i.e., algorithms for which the space of all inputs has a known probability distribution. It also presents two probabilistic algorithms with real-time response for the problem of communication guard scheduling.Google Scholar
SPRUGNOLI, R. 1977. Perfect hash functions: A single probe retrieval method for static sets. Commun. ACM 20, 11, 841-850. This is the first discussion on perfect hashing; it describes heuristics for constructing perfect hash functions. Google ScholarDigital Library
STOCKMEYER, L. 1985. On approximation algorithms for #P. SIAMJ. Comput~ 14, 4, 849-861. 'The author explores the effect of approximation and randomization on the complexity of counting problems (Valiant's class #P which has problems such as counting the number of perfect matchings in a graph, the size of backtrack search trees, etc.).Google Scholar
TODA, S. AND OGIWARA, M. 1992. Counting classes are at least as hard as the polynomial-time hierarchy. SIAM J. Cort*p~t. 21, 2 (Apr.), 316-328. Many counting classes are shown to be computationally as hard as the polynomialtime hierarchy, under a notion of randomized reducibility, unless the polynomial-time hierarchy collapses. Google ScholarDigital Library
TUTrE, W. T. 1947. The factorization of linear graphs. J. London Math. Soc. 22, 107-111. Let G(V, E) be a given simple graph where V = {1, 2 .. n}. Associate a variable x,j with each edge e~j c E and define the n x n matrix B = b,j as follows. If there is no edge between vertex i and vertex j them b~j = 0. Otherwise,b~j = x,j if i >j and b~j = -x~j if i <j. This paper proves that G has a perfect matching if and only if det(B) ~ 0.Google ScholarCross Ref
ULLMAN, J. D. AND YANNAKAKIS, M. 1991. Highprobability parallel transitive closure algorithms. SIAM J. Comput. 20, 1 (Feb.), 100 125. Parallel transitive-closure algorithms are presented for the case when the graph is sparse or only a single source information is desired. The algorithms presented can converted to the Las Vegas type. Google ScholarDigital Library
UPFAL, E. 1989. An O(log N) deterministic packet routing scheme. In Proceedings of the 21st Annual ACM Symposium on the Theory of Computing. ACM, New York, 241-250. This paper presents the first deterministic O(log N) permutation routing algorithm for a multibutterfly network. A multibutterfiy network is a special instance of a delta network. Upfal also shows that P instances of the permutation problem can be routed in O(log N + P) steps using a pipelining approach. Google ScholarDigital Library
UNITED STATES DEPARTMENT OF DEFENSE. 1983. Reference Manual for the Ada Programming Language. MIL-STD 1815A, U.S. Dept. of Defense, Washington, D.C. Section 3.2 of our survey discusses a randomized distributed algorithm for the scheduling of input and output guards. The designers of Ada chose only to allow nondeterministic choice among the accept alternatives of a select statement. This design decision makes the guard-scheduling problem in Ada much easier and, in particular, obliviates the need for randomization.Google Scholar
VALIANT, L.G. 1984a. Short monotone formulae for the majority function. J. Alg. 5, 3, 363 366. A probabilistic approximation of a deterministic boolean function can yield simple circuits having a small proportion of inputs that cause wrong outputs. Independent probabilistic approximations of the same function can be combined to reduce the probability of error. In this paper Valiant uses such a technique to obtain O(n53)-size monotone formulas that compute the majority function of n boolean variables.Google ScholarCross Ref
VALIANT, L.G. 1984b. A theory of the learnable. Commun. ACM 27, 11, 1134-1142. Valiant introduces a formal framework for the probabilistic analysis of algorithms that learn sets defined on a predetermined universe. Google ScholarDigital Library
VALL~NT, L. G. 1982. A scheme for fast parallel communication. SIAM J. Comput. 11, 2 (May), 350-361. Valiant gives a distributed randomized algorithm for routing packets from unique sources to unique destinations in an n-dimensional binary cube in O(log N) time, where N = 2n is the number of nodes in the network, with high probability.Google Scholar
V~&I~T, L. ANn BREBNER, G. 1981. Universal schemes for parallel communication. In Proceedings of the 13th Annual ACM Symposium on the Theory of Computing. ACM, New York, 263-277. This paper extends Valiant's {1982} message-routing algorithm to asynchronous networks. Google ScholarDigital Library
V~oIs, D. 1987. Algorithmes probabilistes: Une anthologie. Master's thesis, D~partement d'informatique et de recherche op6rationnelle, Universit~ de Montreal. This paper covers a number of probabilistic algorithms including matrix multiplication and inversion, manipulation of polynomials, set equality, Byzantine Generals, and cryptography.Google Scholar
VAN DE SNEPSCHEUT, J. L.h. 1981. Synchronous communication between asynchronous components. Inf. Process. Lett. 13, 3 (Dec.), 127-130. The author presents a distributed algorithm for CSP output guards in which processes are related by a tree structure. A probabilistic algorithm for output guards is described in Section 3.2.Google ScholarCross Ref
V~I~I, U. V. 1987. Efficiency considerations in using semi-random sources. In Proceedtngs of the 19th Annual ACM Sympostum on the Theory of Computing. ACM, New York, 160-168. Efficient algorithms for using semirandom sources are presented. Google ScholarDigital Library
VAZI~I, U. V. AND V^zmANi, V. V. 1989. The two-processor scheduling problem is in random NC. SIAM J. Comput. 18, 6, 1140-1148. An efficient, randomized, parallel solution to the well-studied two-processor scheduling problem is presented. Google ScholarDigital Library
VAZIRANI, U. V. AND VAZIRANI, V.V. 1985. Random polynomial time is equal to semi-random polynomial time. In Proceedings of the 26th Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 417 428. This paper analyzes the behavior of randomized algorithms where perfectly random sources are substituted with sources which have small bias and dependence. It shows that if a problem can be solved by a polynomial-time Monte Carlo algorithm which has access to a true source of randomness, then the same problem can be solved using an arbitrarily weak semirandom source.Google ScholarDigital Library
VISHKIN, U. 1984. Randomized speed-ups in parallel computation. In Proceedings of the 16th Annual ACM Symposium on the Theory of Computing. ACM, New York, 230-239. Vishkin considers the problem of computing the position of each element of a linked list, given the length n of the list. He presents a probabilistic algorithm for this problem with running time O(n/p + log n log* n) using p processors. Google ScholarDigital Library
VI~rER, J. S. AND Ft~JOLET, P. 1990. Averagecase analysis of algorithms and data structures. In Handbook of Theoretical Computer Science. Vol. A. Algorithms and Complexity. Elsevier and The MIT Press, New York/ Cambridge, Mass., 432-524. Vitter and Flajolet present analytic methods for average-case analysis of algorithms, with special emphasis on the main algorithms and data structures used for processing nonnumerical data. Problems considered include sorting, searching, pattern matching, register allocation, tree compaction, retrieval of multidimensional data, and efficient access to large files stored on secondary memory. The main mathematical tools used include generating functions (for recursively defined structures), statistics of inversion tables (for sorting algorithms), and valuations on combinatorial structures (for trees and structures with tree-like recursive decomposition, such as plane trees, multidimensional search trees, quicksort, and algorithms for register allocation and tree compaction). Google ScholarDigital Library
VON ZUR GATHEN, J. 1991. Tests for permutation polynomials. SIAM J. Comput. 20, 3 (June), 591-602. An element of a finite field Fq{ x} is called a permutation polynomial if the mapping Fq -~ Fq induced by it is bijective. A probabilistic algorithm for testing this property is given. Google ScholarDigital Library
VON ZUR GAT~tEN, J. AND SHOUP, V. 1992. Computing Frobenius maps and factoring polynomials. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing. ACM, New York, 97 105. A probabilistic algorithm for factoring univariate polynomials over finite fields is presented whose asymptotic running time improves upon previous results. Google ScholarDigital Library
WEmE, B.W. 1978. Statistical methods in algorithmic design and analysis. Ph.D. thesis, Rep. CMU-CS-78-142, Computer Science Dept., Carnegie-Mellon Univ., Pittsburgh. An early survey of probabilistic algorithms and analysis.Google Scholar
WELSH, D. J.A. 1983. Randomized algorithms. Discr. Appl. Math. 5, 1, 133-146. This is a well-written introduction to randomized algorithms. Welsh discusses probabilistic algorithms for checking polynomial identities, primality, matrix and polynomial multiplication, and deciding whether a graph has a perfect matching. The work also contains a nice discussion on random polynomial time, random logspace, and the probabilistic hierarchy.Google ScholarCross Ref
WHANG, K.-Y., VANDER-ZANDEN, B. T., AND TAYLOR, H. M. 1990. A linear-time probabilistic counting algorithm for database applications. ACM Trans. Database Syst. 15, 2 (Sept.), 208- 229. A probabilistic technique called linear counting, based on hashing, for counting the number of unique values in the presence of duplicates is presented in this paper. Google ScholarDigital Library
WYLLm, J. C. 1979 The complexity of parallel computation. Tech. Rep. TR 79-387, Dept. of Computer Science, Cornell Univ, Ithaca, N.Y. Wyllie conjectures that there is no optimal speedup parallel algorithm for n/log n processors for the problem: given a linked list of length n, compute the distance of each element of the linked list from the end of the list. However, Vishkin showed that such optimal speedup can be obtained via randomization (see Section 4). Google ScholarDigital Library
YAO, A. C. 1991. Lower bounds to randomized algorithms for graph properties, d. Cornput. Syst. Sci. 42, 3, 267-287. Yao shows that ll(n(log n)1/12) edges must be examined by any randomized algorithm (as opposed to 12(n2) by any deterministic algorithm) for determining any nontrivial monotone-graph property. An earlier version of this paper appeared in Proceedings of the 28th Annual IEEE Symposium on the Foundations of Computer Science, 1987. Google ScholarDigital Library
YAO, A. C. 1979 The complexity of pattern matching for a random string. SIAM J. Cornput. 8, 3 (Aug.), 368-387. Yao proves that the minimum average number of characters which need be examined in a random string of length n for locating patterns of length m, in an alphabet with q symbols, is O({logq((nm/ln m)+ 2)1) if m _< n _< 2m and 0(({logq m}/m)n) if n > 2m. This confirms Knuth et al.'s {1977} conjecture.Google Scholar
ZIPPEL, R. 1979. Probabilistic algorithms for sparse polynomials. In ISSAC '79: Procee&ngs of the Internatmnal Symposium on Symbohc and Algebraic Computation. Lecture Notes in Computer Science, vol. 72. Springer-Verlag, New York. Zippel discusses probabilistic methods for testing polynomial identities and properties of systems of polynomials. Google ScholarDigital Library
ZUCKERMAN, D. 1991. Simulating BPP using a general weak random source. In Proceedings of the 32nd Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 79-89. Using the weak random source defined in Zuckerman {1990}, this paper shows how to simulate BPP and approximation algorithms in polynomial time using the output from a such a source. Google ScholarDigital Library
ZUCKERMAN, D 1990. General weak random sources. In Proceedings of the 31st Annual IEEE Symposium on the Foundations of Computer Science. IEEE, New York, 534-543. A pseudorandom generator that depends only on a weak random source is exhibited. By a weak random source it is meant that (1) the source is asked only once for R random bits and (2) the source outputs an R-bit string such that no string has a probability more than 2 sR of being output, for some fixed S > 0. This paper shows how to simulate RP using a string from a &source in time n~(l~g~), or in polynomial time under the Generalized Paley Graph Conjecture. See Zuckerman {1991} for a correction to a result in this paper.Google Scholar

Index Terms

On randomization in sequential and distributed algorithms

Recommendations

An optimal distributed (Δ+1)-coloring algorithm?
STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing

Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper we present a new algorithm for (Δ+1)-list coloring in the randomized LOCAL model running in O(log^∗n + Det_d(poly logn)) time, where Det_d(n′) ...
Read More
Optimal distributed covering algorithms
Abstract
We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is ... $^{}$ $^{}$ $_{}$
$\begin{matrix} ((\frac{}{}^{}^{}^{})) \end{matrix}$
$\{_{}\}$ $_{}$
Read More
Fast deterministic distributed algorithms for sparse spanners
SIROCCO'06: Proceedings of the 13th international conference on Structural Information and Communication Complexity

This paper concerns the efficient construction of sparse and low stretch spanners for unweighted arbitrary graphs with n nodes. All previous deterministic distributed algorithms, for constant stretch spanner of o(n²) edges, have a running time Ω(n^ε) for ...
Read More

Comments

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Published in
ACM Computing Surveys Volume 26, Issue 1
March 1994
132 pages
ISSN:0360-0300
EISSN:1557-7341
DOI:10.1145/174666
Editor:
Richard R. Muntz
Univ. of California, Los Angeles
Issue’s Table of Contents
Copyright © 1994 ACM
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
In-Cooperation
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
- Published: 1 March 1994
Published in csur Volume 26, Issue 1

Permissions
Request permissions about this article.
Request Permissions

Check for updates
Author Tags
Byzantine agreement
CSP
analysis of algorithms
computational complexity
dining philosophers problem
distributed algorithms
graph isomorphism
hashing
interactive probabilistic proof systems
leader election
message routing
nearest-neighbors problem
perfect hashing
primality testing
probabilistic techniques
randomized or probabilistic algorithms
randomized quicksort
sequential algorithms
transitive tournaments
universal hashing
Qualifiers
- article
Conference
Funding Sources
Other Metrics
View Article Metrics

Article Metrics
- 43
  Total Citations
  View Citations
- 3,620
  Total Downloads
- Downloads (Last 12 months)101
- Downloads (Last 6 weeks)11
Other Metrics
View Author Metrics
Cited By
View all

PDF Format

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

On randomization in sequential and distributed algorithms

ACM Computing Surveys

Abstract

References

Cited By

Index Terms

Recommendations

An optimal distributed (Δ+1)-coloring algorithm?

Optimal distributed covering algorithms

Fast deterministic distributed algorithms for sparse spanners

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Funding Sources

Other Metrics

Article Metrics

Other Metrics

Cited By

PDF Format

eReader

Digital Edition

Caption

On randomization in sequential and distributed algorithms

ACM Computing Surveys

Abstract

References

Cited By

Index Terms

Recommendations

An optimal distributed (Δ+1)-coloring algorithm?

Optimal distributed covering algorithms

Fast deterministic distributed algorithms for sparse spanners

Comments

Login options

Full Access

Published in

Sponsors

In-Cooperation

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Funding Sources

Article Metrics

Other Metrics

PDF Format

eReader

Digital Edition

Share this Publication link

Share on Social Media