|
 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
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
|
| |
2
|
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.
|
 |
3
|
|
| |
4
|
|
| |
5
|
|
| |
6
|
|
| |
7
|
|
| |
8
|
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}.
|
| |
9
|
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
|
| |
14
|
|
| |
15
|
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.
|
| |
16
|
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.
|
| |
17
|
|
| |
18
|
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.
|
| |
19
|
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.
|
| |
20
|
|
| |
21
|
|
| |
22
|
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.
|
| |
23
|
|
| |
24
|
|
| |
25
|
|
| |
26
|
|
| |
27
|
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.
|
| |
28
|
|
| |
29
|
|
| |
30
|
|
| |
31
|
Yair Bartal , Amos Fiat , Howard Karloff , Rakesh Vohra, New algorithms for an ancient scheduling problem, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.51-58, May 04-06, 1992, Victoria, British Columbia, Canada
[doi> 10.1145/129712.129718]
|
| |
32
|
|
| |
33
|
|
| |
34
|
Richard Beigel , Nick Reingold , Daniel Spielman, PP is closed under intersection, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.1-9, May 05-08, 1991, New Orleans, Louisiana, United States
[doi> 10.1145/103418.103426]
|
| |
35
|
|
| |
36
|
|
| |
37
|
M. Bellare , S. Goldwasser , C. Lund , A. Russeli, Efficient probabilistically checkable proofs and applications to approximations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.294-304, May 16-18, 1993, San Diego, California, United States
[doi> 10.1145/167088.167174]
|
| |
38
|
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.
|
| |
39
|
M. Bellare , S. Micali , R. Ostrovsky, Perfect zero-knowledge in constant rounds, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.482-493, May 13-17, 1990, Baltimore, Maryland, United States
[doi> 10.1145/100216.100283]
|
| |
40
|
S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States
[doi> 10.1145/100216.100268]
|
| |
41
|
|
| |
42
|
|
| |
43
|
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.
|
| |
44
|
Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States
[doi> 10.1145/62212.62223]
|
| |
45
|
Michael Ben-Or , Shafi Goldwasser , Avi Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.1-10, May 02-04, 1988, Chicago, Illinois, United States
[doi> 10.1145/62212.62213]
|
| |
46
|
|
| |
47
|
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}.
|
| |
48
|
|
| |
49
|
|
| |
50
|
|
| |
51
|
|
| |
52
|
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.
|
| |
53
|
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).
|
| |
54
|
|
| |
55
|
M. Blum , M. Luby , R. Rubinfeld, Self-testing/correcting with applications to numerical problems, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.73-83, May 13-17, 1990, Baltimore, Maryland, United States
[doi> 10.1145/100216.100225]
|
| |
56
|
Manuel Blum , Paul Feldman , Silvio Micali, Non-interactive zero-knowledge and its applications, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.103-112, May 02-04, 1988, Chicago, Illinois, United States
[doi> 10.1145/62212.62222]
|
| |
57
|
|
| |
58
|
|
| |
59
|
|
| |
60
|
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 given
|
| |
61
|
|
| |
62
|
|
| |
63
|
|
| |
64
|
|
| |
65
|
|
| |
66
|
|
| |
67
|
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.
|
| |
68
|
|
| |
69
|
|
| |
70
|
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.
|
| |
71
|
|
| |
72
|
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).
|
| |
73
|
|
| |
74
|
|
| |
75
|
|
| |
76
|
|
| |
77
|
Suresh Chari , Pankaj Rohatgi , Aravind Srinivasan, Randomness-optimal unique element isolation, with applications to perfect matching and related problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.458-467, May 16-18, 1993, San Diego, California, United States
[doi> 10.1145/167088.167213]
|
| |
78
|
David Chaum , Claude Crépeau , Ivan Damgard, Multiparty unconditionally secure protocols, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.11-19, May 02-04, 1988, Chicago, Illinois, United States
[doi> 10.1145/62212.62214]
|
| |
79
|
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."
|
| |
80
|
|
| |
81
|
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.
|
| |
82
|
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.
|
| |
83
|
|
| |
84
|
|
| |
85
|
|
| |
86
|
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.
|
| |
87
|
Anne Condon , Joan Feigenbaum , Carsten Lund , Peter Shor, Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.305-314, May 16-18, 1993, San Diego, California, United States
[doi> 10.1145/167088.167190]
|
| |
88
|
|
| |
89
|
|
| |
90
|
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.
|
| |
91
|
|
| |
92
|
|
| |
93
|
|
| |
94
|
|
| |
95
|
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.
|
| |
96
|
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.
|
| |
97
|
|
| |
98
|
|
| |
99
|
|
| |
100
|
|
| |
101
|
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.
|
| |
102
|
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.
|
| |
103
|
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.
|
| |
104
|
|
| |
105
|
|
| |
106
|
|
| |
107
|
|
| |
108
|
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.
|
| |
109
|
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.
|
| |
110
|
|
| |
111
|
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.
|
| |
112
|
|
| |
113
|
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.
|
| |
114
|
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).
|
| |
115
|
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.
|
| |
116
|
|
| |
117
|
|
| |
118
|
|
| |
119
|
|
| |
120
|
|
| |
121
|
|
| |
122
|
|
| |
123
|
|
| |
124
|
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).
|
| |
125
|
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.
|
| |
126
|
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.
|
| |
127
|
|
| |
128
|
|
| |
129
|
|
| |
130
|
|
| |
131
|
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.
|
| |
132
|
|
| |
133
|
|
| |
134
|
|
| |
135
|
|
| |
136
|
|
| |
137
|
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.
|
| |
138
|
|
| |
139
|
S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States
[doi> 10.1145/22145.22178]
|
| |
140
|
|
| |
141
|
Mordecai Golin , Rajeev Raman , Christian Schwarz , Michiel Smid, Randomized data structures for the dynamic closest-pair problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.301-310, January 25-27, 1993, Austin, Texas, United States
|
| |
142
|
|
| |
143
|
|
| |
144
|
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.
|
| |
145
|
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 methods
|
| |
146
|
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.
|
| |
147
|
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.
|
| |
148
|
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.
|
| |
149
|
|
| |
150
|
|
| |
151
|
|
| |
152
|
|
| |
153
|
|
| |
154
|
|
| |
155
|
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.
|
| |
156
|
R. Impagliazzo , L. A. Levin , M. Luby, Pseudo-random generation from one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.12-24, May 14-17, 1989, Seattle, Washington, United States
[doi> 10.1145/73007.73009]
|
| |
157
|
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.
|
| |
158
|
|
| |
159
|
|
| |
160
|
|
| |
161
|
|
| |
162
|
|
| |
163
|
Ming-Yang Kao , John H. Reif , Stephen R. Tate, Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.441-447, January 25-27, 1993, Austin, Texas, United States
|
| |
164
|
|
| |
165
|
|
| |
166
|
|
| |
167
|
|
| |
168
|
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.
|
| |
169
|
|
| |
170
|
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}.
|
| |
171
|
|
| |
172
|
|
| |
173
|
Richard M. Karp , Michael Luby , Friedhelm Meyer auf der Heide, Efficient PRAM simulation on a distributed memory machine, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.318-326, May 04-06, 1992, Victoria, British Columbia, Canada
[doi> 10.1145/129712.129743]
|
| |
174
|
|
| |
175
|
|
| |
176
|
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.
|
| |
177
|
Z. M. Kedem , K. V. Palem , M. O. Rabin , A. Raghunathan, Efficient program transformations for resilient parallel computation via randomization (preliminary version), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.306-317, May 04-06, 1992, Victoria, British Columbia, Canada
[doi> 10.1145/129712.129742]
|
| |
178
|
|
| |
179
|
|
| |
180
|
|
| |
181
|
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.
|
| |
182
|
|
| |
183
|
|
| |
184
|
P. Klein , C. Stein , É. Tardos, Leighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.310-321, May 13-17, 1990, Baltimore, Maryland, United States
[doi> 10.1145/100216.100257]
|
| |
185
|
|
| |
186
|
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.
|
| |
187
|
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."
|
| |
188
|
|
| |
189
|
|
| |
190
|
Eyal Kushilevitz , Yishay Mansour , Michael O. Rabin , David Zuckerman, Lower bounds for randomized mutual exclusion, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.154-163, May 16-18, 1993, San Diego, California, United States
[doi> 10.1145/167088.167139]
|
| |
191
|
|
| |
192
|
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.
|
| |
193
|
|
| |
194
|
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.
|
| |
195
|
|
| |
196
|
|
| |
197
|
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.
|
| |
198
|
Tom Leighton , Clifford Stein , Fillia Makedon , Éva Tardos , Serge Plotkin , Spyros Tragoudas, Fast approximation algorithms for multicommodity flow problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.101-111, May 05-08, 1991, New Orleans, Louisiana, United States
[doi> 10.1145/103418.103425]
|
| |
199
|
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.
|
| |
200
|
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.
|
| |
201
|
|
| |
202
|
|
| |
203
|
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.
|
| |
204
|
|
| |
205
|
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.
|
| |
206
|
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}.
|
| |
207
|
|
| |
208
|
|
| |
209
|
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.
|
| |
210
|
|
| |
211
|
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.
|
| |
212
|
Udi Manber , Martin Tompa, Probabilistic, nondeterministic, and alternating decision trees (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.234-244, May 05-07, 1982, San Francisco, California, United States
[doi> 10.1145/800070.802197]
|
| |
213
|
|
| |
214
|
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.
|
| |
215
|
|
| |
216
|
Yossi Matias , Jeffrey Scott Vitter , Wen-Chun Ni, Dynamic generation of discrete random variates, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.361-370, January 25-27, 1993, Austin, Texas, United States
|
| |
217
|
Jiří Matoušek , David M. Mount , Nathan S. Netanyahu, Efficient randomized algorithms for the repeated median line estimator, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.74-82, January 25-27, 1993, Austin, Texas, United States
|
| |
218
|
|
| |
219
|
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.
|
| |
220
|
|
| |
221
|
|
| |
222
|
|
| |
223
|
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.
|
| |
224
|
|
| |
225
|
|
| |
226
|
|
| |
227
|
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.
|
| |
228
|
|
| |
229
|
|
| |
230
|
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}.
|
| |
231
|
|
| |
232
|
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}.
|
| |
233
|
|
| |
234
|
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.
|
| |
235
|
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.
|
| |
236
|
|
| |
237
|
|
| |
238
|
|
| |
239
|
|
| |
240
|
|
| |
241
|
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).
|
| |
242
|
|
| |
243
|
|
| |
244
|
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}.
|
| |
245
|
|
| |
246
|
|
| |
247
|
|
| |
248
|
|
| |
249
|
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.
|
| |
250
|
|
| |
251
|
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.
|
| |
252
|
|
| |
253
|
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.
|
| |
254
|
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}.
|
| |
255
|
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.
|
| |
256
|
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.
|
| |
257
|
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.
|
| |
258
|
|
| |
259
|
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.
|
| |
260
|
|
| |
261
|
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.
|
| |
262
|
|
| |
263
|
|
| |
264
|
|
| |
265
|
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.
|
| |
266
|
|
| |
267
|
|
| |
268
|
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}.
|
| |
269
|
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.
|
| |
270
|
|
| |
271
|
|
| |
272
|
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.
|
| |
273
|
|
| |
274
|
|
| |
275
|
Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding bounds for applications with limited independence, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.331-340, January 25-27, 1993, Austin, Texas, United States
|
| |
276
|
|
| |
277
|
|
| |
278
|
|
| |
279
|
|
| |
280
|
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.
|
| |
281
|
|
| |
282
|
|
| |
283
|
|
| |
284
|
|
| |
285
|
|
| |
286
|
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.
|
| |
287
|
|
| |
288
|
SMITH, J. 1983. Public key cryptography. Byte 8, 1 (Jan.), 198-218. This is a simple exposition of public-key cryptography.
|
| |
289
|
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.
|
| |
290
|
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.
|
| |
291
|
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.
|
| |
292
|
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.
|
| |
293
|
|
| |
294
|
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.).
|
| |
295
|
|
| |
296
|
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.
|
| |
297
|
|
| |
298
|
|
| |
299
|
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.
|
| |
300
|
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.
|
| |
301
|
|
| |
302
|
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.
|
| |
303
|
|
| |
304
|
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.
|
| |
305
|
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.
|
| |
306
|
|
| |
307
|
|
| |
308
|
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.
|
| |
309
|
|
| |
310
|
|
| |
311
|
|
| |
312
|
|
| |
313
|
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.
|
| |
314
|
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.
|
| |
315
|
|
| |
316
|
|
| |
317
|
|
| |
318
|
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.
|
| |
319
|
|
| |
320
|
|
| |
321
|
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.
|
CITED BY 10
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
David N. Jansen , Joost-Pieter Katoen , Marcel Oldenkamp , Mariëlle Stoelinga , Ivan Zapreev, How fast and fat is your probabilistic model checker? an experimental performance comparison, Proceedings of the 3rd international Haifa verification conference on Hardware and software: verification and testing, October 23-25, 2007, Haifa, Israel
|
|
|
|
|
|
|
|
|
|
INDEX TERMS
Primary Classification:
G.
Mathematics of Computing
G.3
PROBABILITY AND STATISTICS
Subjects:
Probabilistic algorithms (including Monte Carlo)
Additional Classification:
D.
Software
D.1
PROGRAMMING TECHNIQUES
F.
Theory of Computation
F.1
COMPUTATION BY ABSTRACT DEVICES
F.1.2
Modes of Computation
Subjects:
Probabilistic computation
General Terms:
Algorithms
Keywords:
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
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf