2936:(a finite set of reactions like A+B → 2C + D operating on a finite number of molecules), the ability to ever reach a given target state from an initial state is decidable, while even approximating the probability of ever reaching a given target state (using the standard concentration-based probability for which reaction will occur next) is undecidable. More specifically, a limited Turing machine can be simulated with arbitrarily high probability of running correctly for all time, only if a random chemical reaction network is used. With a simple nondeterministic chemical reaction network (any possible reaction can happen next), the computational power is limited to
1187:
1195:
2623:
769:), by having it output an arbitrary, possibly incorrect answer if it fails to complete within a specified time. Conversely, if an efficient verification procedure exists to check whether an answer is correct, then a Monte Carlo algorithm can be converted into a Las Vegas algorithm by running the Monte Carlo algorithm repeatedly till a correct answer is obtained.
2816:, it is currently an open question whether the ability to make random choices allows some problems to be solved in polynomial time that cannot be solved in polynomial time without this ability; this is the question of whether P = BPP. However, in other contexts, there are specific examples of problems where randomization yields strict improvements.
2272:
2839:
is to provide a result that approximates the correct one with high probability (or
Probably Approximately Correct Computation (PACC)). The hard problem associated with the evaluation of the discrepancy loss between the approximated and the correct computation can be effectively addressed by resorting
1013:
gave his first application of the probabilistic method in 1947, when he used a simple randomized construction to establish the existence of Ramsey graphs. He famously used a much more sophisticated randomized algorithm in 1959 to establish the existence of graphs with high girth and chromatic number.
1077:
is to randomly permute the input points and then insert them one by one into the existing structure. The randomization ensures that the expected number of changes to the structure caused by an insertion is small, and so the expected running time of the algorithm can be bounded from above. This
806:
for which there is an efficient (polynomial time) randomized algorithm (or probabilistic Turing machine) which recognizes NO-instances with absolute certainty and recognizes YES-instances with a probability of at least 1/2. The complement class for RP is co-RP. Problem classes having (possibly
1044:
numbers for some well-defined class of degenerate inputs (such as an already sorted array), with the specific class of inputs that generate this behavior defined by the protocol for pivot selection. However, if the algorithm selects pivot elements uniformly at random, it has a provably high
2078:
186:
bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random determined by the random bits; thus either the running time, or the output (or both) are random variables.
3249:
Mathematics of
Computation 1943–1993: a half-century of computational mathematics; Papers from the Symposium on Numerical Analysis and the Minisymposium on Computational Number Theory held in Vancouver, British Columbia, August 9–13,
3098:
will cause the computer to make an error in carrying out a 'correct' algorithm. Considering an algorithm to be inadequate for the first reason but not for the second illustrates the difference between mathematics and engineering."
2066:
1732:
213:
in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior and mathematical guarantees which may depend on the existence of an ideal true random number generator.
430:
742:. In cryptographic applications, pseudo-random numbers cannot be used, since the adversary can predict them, making the algorithm effectively deterministic. Therefore, either a source of truly random numbers or a
2743:, i.e., we do not know whether we can take an arbitrary randomized algorithm that runs in polynomial time with a small error probability and derandomize it to run in polynomial time without using randomness.
958:
performed the first correct analysis of linear probing, although the memorandum containing his analysis was not published until much later. The first published analysis was due to
Konheim and Weiss in 1966.
2913:
showed that no deterministic algorithm can do the same. This is true unconditionally, i.e. without relying on any complexity-theoretic assumptions, assuming the convex body can be queried only as a black
2267:{\displaystyle \Pr\geq \left({\frac {n-2}{n}}\right)\left({\frac {n-3}{n-1}}\right)\left({\frac {n-4}{n-2}}\right)\ldots \left({\frac {3}{5}}\right)\left({\frac {2}{4}}\right)\left({\frac {1}{3}}\right).}
2419:
686:
This algorithm does not guarantee success, but the run time is bounded. The number of iterations is always less than or equal to k. Taking k to be constant the run time (expected and absolute) is
2803:
all possible parameters (seeds) of the hash function. This technique is usually used to exhaustively search a sample space and making the algorithm deterministic (e.g. randomized graph algorithms)
2921:. IP consists of all languages that can be accepted (with high probability) by a polynomially long interaction between an all-powerful prover and a verifier that implements a BPP algorithm. IP =
1282:
times executions of the outer loop, we output the minimum cut among all the results. The figure 2 gives an example of one execution of the algorithm. After execution, we get a cut of size 3.
1079:
2346:
2731:
randomness (or using as little of it as possible). It is not currently known if all algorithms can be derandomized without significantly increasing their running time. For instance, in
2478:
1881:
206:
problem) or fail to produce a result either by signaling a failure or failing to terminate. In some cases, probabilistic algorithms are the only practical means of solving a problem.
2607:
1940:
2544:
2511:
681:
1005:
popularized the use of randomized constructions as a mathematical technique for establishing the existence of mathematical objects. This technique has become known as the
190:
There is a distinction between algorithms that use the random input so that they always terminate with the correct answer, but where the expected running time is finite (
2900:
1245:
In each execution of the outer loop, the algorithm repeats the inner loop until only 2 nodes remain, the corresponding cut is obtained. The run time of one execution is
969:
Early work on randomized data structures also extended beyond hash tables. In 1970, Burton Howard Bloom introduced an approximate-membership data structure known as the
713:
462:
1610:
962:
Early works on hash tables either assumed access to a fully random hash function or assumed that the keys themselves were random. In 1979, Carter and Wegman introduced
753:
In the example above, the Las Vegas algorithm always outputs the correct answer, but its running time is a random variable. The Monte Carlo algorithm (related to the
1491:
2871:
4197:
1272:
743:
1607:
The probability that the algorithm succeeds is 1 − the probability that all attempts fail. By independence, the probability that all attempts fail is
1948:
850:, which finds the median element of a list in linear expected time. It remained open until 1973 whether a deterministic linear-time algorithm existed.
3109:
352:
This algorithm succeeds with probability 1. The number of iterations varies and can be arbitrarily large, but the expected number of iterations is
3612:
358:
4190:
1190:
Figure 2: Successful run of Karger's algorithm on a 10-vertex graph. The minimum cut has size 3 and is indicated by the vertex colours.
2695:
935:
757:
for simulation) is guaranteed to complete in an amount of time that can be bounded by a function the input size and its parameter
4183:
3005:
2667:
727:
150:
4038:
Semantics of the
Probabilistic Typed Lambda Calculus (Markov Chain Semantics, Termination Behavior, and Denotational Semantics).
1030:
is a familiar, commonly used algorithm in which randomness can be useful. Many deterministic versions of this algorithm require
2740:
819:
34:
2351:
4124:
3983:
3757:
3588:
3356:
3265:
2644:
17:
2674:
3376:
2995:
1505:
Thus, at the end of the algorithm, we have two compound nodes covering the entire graph, one consisting of the vertices of
2751:
883:
3711:
939:
2820:
Based on the initial motivating example: given an exponentially long string of 2 characters, half a's and half b's, a
2681:
4028:
3876:
3782:
3555:
3540:
3310:
2714:
986:
3252:, Proceedings of Symposia in Applied Mathematics, vol. 48, Amer. Math. Soc., Providence, RI, pp. 481–531,
2652:
874:
introduced a randomized algorithm for efficiently computing the roots of a polynomial over a finite field. In 1977,
2828:; if it is permitted to make random choices, it can solve this problem in an expected polynomial number of lookups.
3788:. For the deterministic lower bound see p. 11; for the logarithmic randomized upper bound see pp. 31–32.
2905:
The volume of a convex body can be estimated by a randomized algorithm to arbitrary precision in polynomial time.
4449:
2663:
2279:
895:
818:
The class of problems for which both YES and NO-instances are allowed to be identified with some error is called
777:
183:
3118:
2424:
4444:
2990:
2950:
2648:
1825:
966:, which they showed could be used to implement chained hash tables with constant expected time per operation.
210:
103:
898:
could also be turned into a polynomial-time randomized algorithm. At that time, no provably polynomial-time
4375:
4345:
4330:
782:
2549:
1901:
143:
4400:
4274:
4264:
4244:
4019:
3060:
Kudelić, Robert (2016-04-01). "Monte-Carlo randomized algorithm for minimal feedback arc set problem".
863:
2516:
2483:
922:. Luhn's hash table used chaining to resolve collisions and was also one of the first applications of
4279:
3279:; see p. 504, "Perhaps Pocklington also deserves credit as the inventor of the randomized algorithm".
2933:
859:
607:
3859:
3209:
Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. (August 1973).
2766:
the exploitation of limited independence in the random variables used by the algorithm, such as the
2727:
Randomness can be viewed as a resource, like space and time. Derandomization is then the process of
3725:
2844:
2633:
203:
3845:
2688:
1186:
4418:
4380:
3210:
2955:
2746:
There are specific methods that can be employed to derandomize particular randomized algorithms:
2637:
1807:
899:
2876:
689:
438:
4224:
4112:
3854:
3720:
2732:
1074:
1066:
766:
164:
136:
1215:
Take a random edge (u,v) ∈ E in G replace u and v with the contraction u'
1183:. After contraction, the resulting graph may have parallel edges, but contains no self loops.
4284:
4254:
3091:
3000:
2985:
2975:
2917:
A more complexity-theoretic example of a place where randomness appears to help is the class
2836:
2821:
2799:
as a source of randomness for the algorithm's tasks, and then derandomizing the algorithm by
2788:
a limited amount of initial randomness (this last approach is also referred to as generating
2767:
2755:
1470:
1091:
791:
731:
723:
270:
199:
3090:
of very large numbers chosen at random, the chance of stumbling upon a value that fools the
2850:
4395:
4315:
4080:
4006:
3295:
Proceedings of the second ACM symposium on
Symbolic and algebraic manipulation - SYMSAC '71
3275:
2965:
1006:
227:
65:
3696:
1248:
765:. Observe that any Las Vegas algorithm can be converted into a Monte Carlo algorithm (via
8:
4405:
4390:
4335:
3962:
2980:
2937:
787:
718:
Randomized algorithms are particularly useful when faced with a malicious "adversary" or
266:
191:
3290:
1379:
without any edge between them. So the min cut in a disconnected graph is 0. Now, assume
4423:
4325:
4320:
4234:
3921:
3882:
3847:
Proc. 18th ACM Symposium on Theory of
Computing (Berkeley, California, May 28–30, 1986)
3841:
3824:
3807:
3799:
3678:
3606:
3501:
3316:
2910:
2800:
2760:
1121:
754:
465:
93:
4105:
3709:
Karger, David R. (1999). "Random
Sampling in Cut, Flow, and Network Design Problems".
3226:
2873:
bits of communication with a randomized protocol. Any deterministic protocol requires
4385:
4229:
4152:
4135:
4120:
4024:
3979:
3872:
3778:
3753:
3682:
3670:
3594:
3584:
3536:
3493:
3452:
3447:
3430:
3411:
3352:
3306:
3261:
3191:
3152:
3104:
3042:
2771:
2061:{\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}}
978:
963:
875:
4168:"Randomized Algorithms for Scientific Computing" (RASC), OSTI.GOV (July 10th, 2021).
3886:
3828:
4365:
4350:
4147:
4069:
4010:
4002:
3971:
3911:
3864:
3816:
3730:
3660:
3528:
3505:
3483:
3442:
3403:
3320:
3298:
3253:
3240:
3222:
3183:
3144:
3095:
3069:
3034:
2906:
2832:
1144:
931:
891:
846:
in 1959, and subsequently published in 1961. In the same year, Hoare published the
812:
803:
795:
747:
3925:
3800:"A random polynomial-time algorithm for approximating the volume of convex bodies"
3257:
1727:{\displaystyle \prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).}
4340:
4175:
4035:
3975:
3564:(PS, PDF) (Technical report). Dept. of Computer Science, U. Maryland. CS-TR-2222.
3271:
3244:
2926:
2918:
915:
879:
871:
808:
799:
70:
4206:
4094:
4031:. Chapter 5: Probabilistic Analysis and Randomized Algorithms, pp. 91–122.
4014:
3171:
3132:
3087:
3073:
2813:
2777:
2736:
1032:
974:
947:
887:
823:
46:
27:
Algorithm that employs a degree of randomness as part of its logic or procedure
3945:; Bruck, Jehoshua (2009), "Programmability of chemical reaction networks", in
2792:
bits from a random source, and leads to the related topic of pseudorandomness)
4438:
4355:
4310:
4045:
3674:
3598:
3520:
3497:
3456:
3415:
3195:
3156:
3046:
2796:
951:
4073:
4049:
3532:
1010:
1002:
4305:
4269:
4239:
4089:
Probability and
Computing: Randomized Algorithms and Probabilistic Analysis
3958:
3954:
3942:
3938:
3665:
3648:
3371:
2925:. However, if it is required that the verifier be deterministic, then IP =
2789:
1100:
970:
955:
943:
811:
average case running time whose output is always correct are said to be in
739:
60:
55:
3916:
3820:
3734:
3578:
3560:
3488:
3471:
3348:
The art of computer programming, volume 3: (2nd ed.) sorting and searching
3302:
3247:(1994), "Factoring integers before computers", in Gautschi, Walter (ed.),
3187:
3148:
3038:
1001:
Prior to the popularization of randomized algorithms in computer science,
4259:
3950:
3946:
3100:
2970:
1070:
927:
923:
867:
847:
124:
84:
3868:
3346:
2847:, the equality of two strings can be verified to some reliability using
198:), and algorithms which have a chance of producing an incorrect result (
4249:
3899:
3625:
P. Erdős: Some remarks on the theory of graphs, Bull. Amer. Math. Soc.
1194:
911:
843:
735:
425:{\displaystyle \lim _{n\to \infty }\sum _{i=1}^{n}{\frac {i}{2^{i}}}=2}
179:
4167:
4210:
4084:
3391:
3351:. USA: Addison Wesley Longman Publishing Co., Inc. pp. 536–549.
3114:
2781:
1027:
990:
839:
195:
175:
75:
3407:
2622:
1592:. But it is well known that the sum of vertex degrees equals 2|
826:, i.e. BPP represents the class of efficient randomized algorithms.
593:’ is found, the algorithm succeeds, else the algorithm fails. After
2960:
1060:
719:
209:
In common practice, randomized algorithms are approximated using a
3297:. Los Angeles, California, United States: ACM Press. p. 223.
4360:
1219:
only 2 nodes remain obtain the corresponding cut result C
722:
who deliberately tries to feed a bad input to the algorithm (see
1159:' with edges that are the union of the edges incident on either
182:
as part of its logic or procedure. The algorithm typically uses
163:"Randomized algorithms" redirects here. Not to be confused with
4060:
Fallis, D. (2000). "The reliability of randomized algorithms".
3970:, Natural Computing Series, Springer-Verlag, pp. 543–584,
2922:
2348:. Thus the probability that the algorithm succeeds is at least
435:
Since it is constant, the expected run time over many calls is
746:
is required. Another area in which randomness is inherent is
2824:
requires 2 lookups in the worst-case to find the index of an
2071:
So by the chain rule, the probability of finding the min cut
982:
222:
As a motivating example, consider the problem of finding an ‘
98:
3472:"Space/time trade-offs in hash coding with allowable errors"
4289:
3937:
2831:
The natural way of carrying out a numerical computation in
798:
are studied. The most basic randomized complexity class is
4164:, Mathematics of Operations Research, 24(2):383–413, 1999.
3844:; Bárány, I. (1986), "Computing the volume is difficult",
3583:. Joel H. Spencer (Fourth ed.). Hoboken, New Jersey.
981:
introduced a randomized balanced search tree known as the
4162:
Random
Sampling in Cut, Flow, and Network Design Problems
919:
3525:
30th Annual
Symposium on Foundations of Computer Science
3025:
Hoare, C. A. R. (July 1961). "Algorithm 64: Quicksort".
2414:{\displaystyle 1-\left(1-{\frac {2}{n(n-1)}}\right)^{m}}
1057:) time regardless of the characteristics of the input.
989:
introduced another randomized search tree known as the
744:
cryptographically secure pseudo-random number generator
4111:
910:
One of the earliest randomized data structures is the
4130:
Chapter 11: Randomized computation, pp. 241–278.
3697:
Backwards Analysis of Randomized Geometric Algorithms
2879:
2853:
2552:
2519:
2486:
2427:
2354:
2282:
2081:
1951:
1904:
1828:
1613:
1473:
1251:
1175:. Figure 1 gives an example of contraction of vertex
692:
610:
441:
361:
3208:
1810:. The probability that the edge chosen at iteration
4023:, Second Edition. MIT Press and McGraw–Hill, 1990.
3429:Carter, J. Lawrence; Wegman, Mark N. (1979-04-01).
3390:Konheim, Alan G.; Weiss, Benjamin (November 1966).
2763:(which is used to derandomize geometric algorithms)
2513:. The algorithm finds the min cut with probability
1069:, a standard technique to build a structure like a
4205:
4101:. Cambridge University Press, New York (NY), 1995.
4091:. Cambridge University Press, New York (NY), 2005.
2894:
2865:
2601:
2538:
2505:
2472:
2413:
2340:
2266:
2060:
1934:
1875:
1726:
1485:
1266:
954:independently had the same idea in 1957. In 1962,
822:. This class acts as the randomized equivalent of
707:
675:
456:
424:
4062:The British Journal for the Philosophy of Science
3110:Structure and Interpretation of Computer Programs
996:
4436:
3797:
3772:
3291:"Factoring polynomials over large finite fields"
2283:
2082:
1693:
1635:
1513:. As in figure 2, the size of min cut is 1, and
1061:Randomized incremental constructions in geometry
611:
363:
202:, for example the Monte Carlo algorithm for the
4136:"Probabilistic algorithm for testing primality"
3239:
2812:When the model of computation is restricted to
1588:. Therefore, the sum of the degree is at least
4191:
144:
4160:A. A. Tsay, W. S. Lovejoy, David R. Karger,
3840:
3518:
3428:
3389:
2902:bits if defending against a strong opponent.
1509:and the other consisting of the vertices of
3519:Aragon, C.R.; Seidel, R.G. (October 1989).
2795:changing the randomized algorithm to use a
2651:. Unsourced material may be challenged and
2341:{\displaystyle \Pr\geq {\frac {2}{n(n-1)}}}
1533:) for contraction, we can get the min cut.
1132:, with the minimum number of edges between
862:introduced a randomized algorithm known as
772:
597:iterations, the probability of finding an ‘
265:We give two versions of the algorithm, one
4198:
4184:
3611:: CS1 maint: location missing publisher (
3392:"An Occupancy Discipline and Applications"
3380:, archived from the original on 2016-03-03
2473:{\displaystyle m={\frac {n(n-1)}{2}}\ln n}
151:
137:
4151:
3915:
3858:
3798:Dyer, M.; Frieze, A.; Kannan, R. (1991),
3724:
3664:
3487:
3446:
3288:
2807:
2715:Learn how and when to remove this message
1876:{\displaystyle 1-{\frac {k}{|E(G_{j})|}}}
1602:
1227:i = m output the minimum cut among C
1193:
1185:
3853:, New York, NY: ACM, pp. 442–447,
3773:Kushilevitz, Eyal; Nisan, Noam (2006),
3435:Journal of Computer and System Sciences
3215:Journal of Computer and System Sciences
3059:
3006:Randomized algorithms as zero-sum games
1898:, so by Lemma 2, it still has at least
1198:Figure 1: Contraction of vertex A and B
1155:, in a (multi-)graph yields a new node
728:competitive analysis (online algorithm)
14:
4437:
4059:
4056:. Chapter 13: "Randomized algorithms".
3898:
3747:
3708:
1278:denotes the number of vertices. After
4179:
4133:
3646:
3572:
3570:
3469:
3431:"Universal classes of hash functions"
3344:
3169:
3130:
3024:
1326:be the min cut. If, during iteration
1167:, except from any edge(s) connecting
4108:. A survey on Randomized Algorithms.
3576:
3561:Concurrent Maintenance of Skip Lists
3340:
3338:
3336:
3334:
3332:
3330:
2996:Probabilistic analysis of algorithms
2649:adding citations to reliable sources
2616:
2602:{\displaystyle O(mn)=O(n^{3}\log n)}
1552:vertices and whose min cut has size
3396:SIAM Journal on Applied Mathematics
2752:method of conditional probabilities
1935:{\displaystyle {\frac {(n-j)k}{2}}}
1806:vertices. We use the chain rule of
1751:is the probability that no edge of
1080:randomized incremental construction
902:for primality testing were known.
24:
3712:Mathematics of Operations Research
3567:
2880:
2612:
1759:. Consider the inner loop and let
1340:is selected for contraction, then
914:, which was introduced in 1953 by
905:
693:
633:
627:
624:
621:
618:
442:
373:
25:
4461:
3750:Intelligence for Embedded Systems
3327:
1736:By lemma 1, the probability that
1443:is connected). Consider an edge {
4119:(1st ed.), Addison Wesley,
4104:Rajeev Motwani and P. Raghavan.
2621:
2539:{\displaystyle 1-{\frac {1}{n}}}
2506:{\displaystyle 1-{\frac {1}{n}}}
853:
829:
807:nonterminating) algorithms with
780:models randomized algorithms as
244:≥2 elements, in which half are ‘
3931:
3892:
3834:
3791:
3766:
3741:
3702:
3689:
3653:Canadian Journal of Mathematics
3640:
3619:
3549:
3512:
3463:
3422:
3383:
3365:
1124:partitioning the vertices into
870:modulo prime numbers. In 1970,
778:Computational complexity theory
676:{\displaystyle \Pr=1-(1/2)^{k}}
3777:, Cambridge University Press,
3649:"Graph Theory and Probability"
3470:Bloom, Burton H. (July 1970).
3282:
3233:
3202:
3163:
3124:
3080:
3053:
3018:
2991:Principle of deferred decision
2951:Approximate counting algorithm
2889:
2883:
2596:
2574:
2565:
2556:
2452:
2440:
2394:
2382:
2332:
2320:
2305:
2286:
2104:
2085:
1989:
1985:
1972:
1965:
1920:
1908:
1866:
1862:
1849:
1842:
1718:
1715:
1696:
1684:
1657:
1638:
1261:
1255:
997:Implicit uses in combinatorics
890:of a number). Soon afterwards
702:
696:
664:
649:
637:
614:
451:
445:
370:
13:
1:
3996:
3227:10.1016/S0022-0000(73)80033-9
3170:Hoare, C. A. R. (July 1961).
3131:Hoare, C. A. R. (July 1961).
3094:is less than the chance that
2938:primitive recursive functions
1755:is selected during iteration
1296:be the min cut size, and let
882:discovered a polynomial-time
783:probabilistic Turing machines
734:. It is for this reason that
217:
211:pseudorandom number generator
104:Rapidly exploring random tree
4153:10.1016/0022-314X(80)90084-0
3976:10.1007/978-3-540-88869-7_27
3448:10.1016/0022-0000(79)90044-8
1045:probability of finishing in
1022:
794:are considered, and several
7:
3211:"Time bounds for selection"
2944:
1822:has been chosen before, is
1598:|. The lemma follows.
1465:As long as we pick an edge
1017:
894:demonstrated that the 1976
248:’s and the other half are ‘
10:
4466:
4134:Rabin, Michael O. (1980).
4020:Introduction to Algorithms
3377:Notes on "Open" Addressing
3074:10.1016/j.asoc.2015.12.018
2895:{\displaystyle \Theta (n)}
2754:, and its generalization,
1894:still has min cut of size
1202:Karger's basic algorithm:
1089:
1085:
834:
763:small probability of error
708:{\displaystyle \Theta (1)}
457:{\displaystyle \Theta (1)}
162:
4414:
4298:
4217:
3521:"Randomized search trees"
3476:Communications of the ACM
3345:Knuth, Donald E. (1998).
3289:Berlekamp, E. R. (1971).
3258:10.1090/psapm/048/1314885
3176:Communications of the ACM
3137:Communications of the ACM
3133:"Algorithm 64: Quicksort"
2934:chemical reaction network
1808:conditional possibilities
1774:edge contractions, where
926:. Subsequently, in 1954,
884:randomized primality test
860:Henry Cabourn Pocklington
178:that employs a degree of
4140:Journal of Number Theory
4117:Computational Complexity
3964:Algorithmic Bioprocesses
3775:Communication Complexity
3580:The probabilistic method
3011:
2845:communication complexity
2735:, it is unknown whether
2733:computational complexity
2480:, this is equivalent to
1818:, given that no edge of
1525:)}. If we don't select (
1371:can be partitioned into
964:universal hash functions
900:deterministic algorithms
866:for efficiently finding
802:, which is the class of
773:Computational complexity
473:
278:
4419:List of data structures
3902:(1992), "IP = PSPACE",
3748:Alippi, Cesare (2014),
3533:10.1109/SFCS.1989.63531
2956:Atlantic City algorithm
1770:denote the graph after
1572:Because the min cut is
1486:{\displaystyle f\neq e}
1463:are distinct vertices.
1367:is not connected, then
896:Miller's primality test
886:(i.e., determining the
864:Pocklington's algorithm
471:Monte Carlo algorithm:
4450:Analysis of algorithms
4113:Christos Papadimitriou
3941:; Soloveichik, David;
3666:10.4153/CJM-1959-003-9
3062:Applied Soft Computing
2896:
2867:
2866:{\displaystyle \log n}
2837:cyber-physical systems
2808:Where randomness helps
2756:pessimistic estimators
2664:"Randomized algorithm"
2603:
2540:
2507:
2474:
2415:
2342:
2268:
2062:
1936:
1877:
1728:
1683:
1634:
1487:
1439:} (well-defined since
1268:
1199:
1191:
1078:technique is known as
1075:Delaunay triangulation
1067:computational geometry
792:Monte Carlo algorithms
709:
677:
458:
426:
398:
200:Monte Carlo algorithms
165:Algorithmic randomness
4445:Randomized algorithms
4106:Randomized Algorithms
4099:Randomized Algorithms
4074:10.1093/bjps/51.2.255
3917:10.1145/146585.146609
3821:10.1145/102782.102783
3735:10.1287/moor.24.2.383
3489:10.1145/362686.362692
3303:10.1145/800204.806290
3188:10.1145/366622.366647
3149:10.1145/366622.366644
3039:10.1145/366622.366644
3001:Probabilistic roadmap
2986:Monte Carlo algorithm
2897:
2868:
2822:random-access machine
2768:pairwise independence
2604:
2541:
2508:
2475:
2416:
2343:
2269:
2063:
1937:
1878:
1729:
1663:
1614:
1603:Analysis of algorithm
1548:is a multigraph with
1488:
1269:
1197:
1189:
985:. In the same year,
848:quickselect algorithm
724:worst-case complexity
710:
678:
459:
427:
378:
276:Las Vegas algorithm:
271:Monte Carlo algorithm
18:Randomized complexity
4316:Breadth-first search
4007:Charles E. Leiserson
3527:. pp. 540–545.
3172:"Algorithm 65: find"
2877:
2851:
2645:improve this section
2550:
2517:
2484:
2425:
2352:
2280:
2079:
1949:
1902:
1826:
1611:
1580:must satisfy degree(
1471:
1397:be the partition of
1267:{\displaystyle O(n)}
1249:
1007:probabilistic method
690:
608:
439:
359:
192:Las Vegas algorithms
172:randomized algorithm
120:Randomized algorithm
4406:Topological sorting
4336:Dynamic programming
3869:10.1145/12130.12176
3577:Alon, Noga (2016).
2981:Las Vegas algorithm
2276:Cancellation gives
1542: —
1290: —
936:Nathaniel Rochester
767:Markov's inequality
267:Las Vegas algorithm
4424:List of algorithms
4331:Divide and conquer
4326:Depth-first search
4321:Brute-force search
4235:Binary search tree
3904:Journal of the ACM
3808:Journal of the ACM
3647:Erdös, P. (1959).
2976:Karger's algorithm
2892:
2863:
2761:discrepancy theory
2599:
2536:
2503:
2470:
2411:
2338:
2264:
2058:
1932:
1873:
1724:
1570:
1540:
1503:do not get merged.
1483:
1383:is connected. Let
1361:
1288:
1264:
1200:
1192:
1092:Karger's algorithm
842:was discovered by
796:complexity classes
755:Monte Carlo method
732:Prisoner's dilemma
705:
673:
466:Big Theta notation
454:
422:
377:
94:Random binary tree
4432:
4431:
4230:Associative array
4126:978-0-201-53082-7
4097:and P. Raghavan.
3985:978-3-540-88868-0
3953:; Kok, Joost N.;
3759:978-3-319-05278-6
3629:(1947), 292--294
3590:978-1-119-06195-3
3358:978-0-201-89685-5
3267:978-0-8218-0291-5
3105:Gerald J. Sussman
3088:testing primality
2772:universal hashing
2725:
2724:
2717:
2699:
2534:
2501:
2459:
2398:
2336:
2255:
2237:
2219:
2198:
2164:
2130:
2056:
2021:
1994:
1930:
1871:
1568:
1538:
1359:
1286:
979:Cecilia R. Aragon
876:Robert M. Solovay
804:decision problems
748:quantum computing
738:is ubiquitous in
730:) such as in the
632:
414:
362:
161:
160:
16:(Redirected from
4457:
4401:String-searching
4200:
4193:
4186:
4177:
4176:
4157:
4155:
4129:
4077:
4054:Algorithm Design
4011:Ronald L. Rivest
4003:Thomas H. Cormen
3990:
3988:
3969:
3935:
3929:
3928:
3919:
3896:
3890:
3889:
3862:
3852:
3838:
3832:
3831:
3804:
3795:
3789:
3787:
3770:
3764:
3762:
3745:
3739:
3738:
3728:
3706:
3700:
3693:
3687:
3686:
3668:
3644:
3638:
3623:
3617:
3616:
3610:
3602:
3574:
3565:
3553:
3547:
3546:
3516:
3510:
3509:
3491:
3467:
3461:
3460:
3450:
3426:
3420:
3419:
3402:(6): 1266–1274.
3387:
3381:
3369:
3363:
3362:
3342:
3325:
3324:
3286:
3280:
3278:
3237:
3231:
3230:
3206:
3200:
3199:
3167:
3161:
3160:
3128:
3122:
3096:cosmic radiation
3084:
3078:
3077:
3057:
3051:
3050:
3022:
2966:Count–min sketch
2901:
2899:
2898:
2893:
2872:
2870:
2869:
2864:
2840:to randomization
2833:embedded systems
2720:
2713:
2709:
2706:
2700:
2698:
2657:
2625:
2617:
2608:
2606:
2605:
2600:
2586:
2585:
2545:
2543:
2542:
2537:
2535:
2527:
2512:
2510:
2509:
2504:
2502:
2494:
2479:
2477:
2476:
2471:
2460:
2455:
2435:
2420:
2418:
2417:
2412:
2410:
2409:
2404:
2400:
2399:
2397:
2374:
2347:
2345:
2344:
2339:
2337:
2335:
2312:
2298:
2297:
2273:
2271:
2270:
2265:
2260:
2256:
2248:
2242:
2238:
2230:
2224:
2220:
2212:
2203:
2199:
2197:
2186:
2175:
2169:
2165:
2163:
2152:
2141:
2135:
2131:
2126:
2115:
2097:
2096:
2067:
2065:
2064:
2059:
2057:
2055:
2044:
2027:
2022:
2020:
2006:
1995:
1993:
1992:
1984:
1983:
1968:
1959:
1941:
1939:
1938:
1933:
1931:
1926:
1906:
1893:
1882:
1880:
1879:
1874:
1872:
1870:
1869:
1861:
1860:
1845:
1836:
1805:
1795:
1784:
1769:
1750:
1733:
1731:
1730:
1725:
1708:
1707:
1682:
1677:
1650:
1649:
1633:
1628:
1597:
1543:
1502:
1498:
1494:
1492:
1490:
1489:
1484:
1438:
1396:
1354:
1339:
1325:
1291:
1273:
1271:
1270:
1265:
1143:Recall that the
932:Elaine M. McGraw
892:Michael O. Rabin
714:
712:
711:
706:
682:
680:
679:
674:
672:
671:
659:
636:
630:
585:
582:
579:
576:
573:
570:
567:
564:
561:
558:
555:
552:
549:
546:
543:
540:
537:
534:
531:
528:
525:
522:
519:
516:
513:
510:
507:
504:
501:
498:
495:
492:
489:
486:
483:
480:
477:
463:
461:
460:
455:
431:
429:
428:
423:
415:
413:
412:
400:
397:
392:
376:
348:
345:
342:
339:
336:
333:
330:
327:
324:
321:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
262:’ in the array.
184:uniformly random
153:
146:
139:
66:Count–min sketch
30:
29:
21:
4465:
4464:
4460:
4459:
4458:
4456:
4455:
4454:
4435:
4434:
4433:
4428:
4410:
4341:Graph traversal
4294:
4218:Data structures
4213:
4207:Data structures
4204:
4173:
4127:
4081:M. Mitzenmacher
4042:Springer, 2017.
3999:
3994:
3993:
3986:
3967:
3936:
3932:
3897:
3893:
3879:
3860:10.1.1.726.9448
3850:
3839:
3835:
3802:
3796:
3792:
3785:
3771:
3767:
3760:
3746:
3742:
3707:
3703:
3694:
3690:
3645:
3641:
3624:
3620:
3604:
3603:
3591:
3575:
3568:
3554:
3550:
3543:
3517:
3513:
3468:
3464:
3427:
3423:
3408:10.1137/0114101
3388:
3384:
3370:
3366:
3359:
3343:
3328:
3313:
3287:
3283:
3268:
3241:Williams, H. C.
3238:
3234:
3207:
3203:
3168:
3164:
3129:
3125:
3085:
3081:
3058:
3054:
3023:
3019:
3014:
2947:
2878:
2875:
2874:
2852:
2849:
2848:
2814:Turing machines
2810:
2784:in general) to
2778:expander graphs
2721:
2710:
2704:
2701:
2658:
2656:
2642:
2626:
2615:
2613:Derandomization
2581:
2577:
2551:
2548:
2547:
2526:
2518:
2515:
2514:
2493:
2485:
2482:
2481:
2436:
2434:
2426:
2423:
2422:
2405:
2378:
2373:
2366:
2362:
2361:
2353:
2350:
2349:
2316:
2311:
2293:
2289:
2281:
2278:
2277:
2247:
2243:
2229:
2225:
2211:
2207:
2187:
2176:
2174:
2170:
2153:
2142:
2140:
2136:
2116:
2114:
2110:
2092:
2088:
2080:
2077:
2076:
2045:
2028:
2026:
2010:
2005:
1988:
1979:
1975:
1964:
1963:
1958:
1950:
1947:
1946:
1907:
1905:
1903:
1900:
1899:
1892:
1884:
1865:
1856:
1852:
1841:
1840:
1835:
1827:
1824:
1823:
1797:
1794:
1786:
1775:
1768:
1760:
1745:
1737:
1703:
1699:
1678:
1667:
1645:
1641:
1629:
1618:
1612:
1609:
1608:
1605:
1600:
1593:
1576:, every vertex
1566:
1541:
1535:
1500:
1496:
1472:
1469:
1468:
1466:
1402:
1384:
1357:
1349:
1341:
1331:
1323:
1314:
1307:
1297:
1289:
1250:
1247:
1246:
1243:
1238:
1234:
1230:
1222:
1094:
1088:
1063:
1053: log
1040:) time to sort
1025:
1020:
999:
916:Hans Peter Luhn
908:
906:Data structures
880:Volker Strassen
872:Elwyn Berlekamp
856:
837:
832:
809:polynomial time
775:
761:, but allows a
691:
688:
687:
684:
667:
663:
655:
617:
609:
606:
605:
587:
586:
583:
580:
577:
574:
571:
568:
565:
562:
559:
556:
553:
550:
547:
544:
541:
538:
535:
532:
529:
526:
523:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
490:
487:
484:
481:
478:
475:
440:
437:
436:
408:
404:
399:
393:
382:
366:
360:
357:
356:
350:
349:
346:
343:
340:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
220:
168:
157:
71:Quotient filter
47:data structures
45:
28:
23:
22:
15:
12:
11:
5:
4463:
4453:
4452:
4447:
4430:
4429:
4427:
4426:
4421:
4415:
4412:
4411:
4409:
4408:
4403:
4398:
4393:
4388:
4383:
4378:
4373:
4368:
4363:
4358:
4353:
4348:
4343:
4338:
4333:
4328:
4323:
4318:
4313:
4308:
4302:
4300:
4296:
4295:
4293:
4292:
4287:
4282:
4277:
4272:
4267:
4262:
4257:
4252:
4247:
4242:
4237:
4232:
4227:
4221:
4219:
4215:
4214:
4203:
4202:
4195:
4188:
4180:
4171:
4170:
4165:
4158:
4131:
4125:
4109:
4102:
4095:Rajeev Motwani
4092:
4078:
4068:(2): 255–271.
4057:
4043:
4034:Dirk Draheim.
4032:
4015:Clifford Stein
3998:
3995:
3992:
3991:
3984:
3930:
3910:(4): 869–877,
3891:
3877:
3833:
3790:
3783:
3765:
3758:
3740:
3726:10.1.1.215.794
3719:(2): 383–413.
3701:
3688:
3639:
3618:
3589:
3566:
3558:(April 1989).
3548:
3541:
3511:
3482:(7): 422–426.
3462:
3441:(2): 143–154.
3421:
3382:
3364:
3357:
3326:
3311:
3281:
3266:
3245:Shallit, J. O.
3232:
3221:(4): 448–461.
3201:
3182:(7): 321–322.
3162:
3123:
3079:
3052:
3016:
3015:
3013:
3010:
3009:
3008:
3003:
2998:
2993:
2988:
2983:
2978:
2973:
2968:
2963:
2958:
2953:
2946:
2943:
2942:
2941:
2930:
2915:
2903:
2891:
2888:
2885:
2882:
2862:
2859:
2856:
2841:
2829:
2809:
2806:
2805:
2804:
2793:
2774:
2764:
2758:
2723:
2722:
2705:September 2023
2629:
2627:
2620:
2614:
2611:
2598:
2595:
2592:
2589:
2584:
2580:
2576:
2573:
2570:
2567:
2564:
2561:
2558:
2555:
2533:
2530:
2525:
2522:
2500:
2497:
2492:
2489:
2469:
2466:
2463:
2458:
2454:
2451:
2448:
2445:
2442:
2439:
2433:
2430:
2408:
2403:
2396:
2393:
2390:
2387:
2384:
2381:
2377:
2372:
2369:
2365:
2360:
2357:
2334:
2331:
2328:
2325:
2322:
2319:
2315:
2310:
2307:
2304:
2301:
2296:
2292:
2288:
2285:
2263:
2259:
2254:
2251:
2246:
2241:
2236:
2233:
2228:
2223:
2218:
2215:
2210:
2206:
2202:
2196:
2193:
2190:
2185:
2182:
2179:
2173:
2168:
2162:
2159:
2156:
2151:
2148:
2145:
2139:
2134:
2129:
2125:
2122:
2119:
2113:
2109:
2106:
2103:
2100:
2095:
2091:
2087:
2084:
2054:
2051:
2048:
2043:
2040:
2037:
2034:
2031:
2025:
2019:
2016:
2013:
2009:
2004:
2001:
1998:
1991:
1987:
1982:
1978:
1974:
1971:
1967:
1962:
1957:
1954:
1929:
1925:
1922:
1919:
1916:
1913:
1910:
1888:
1868:
1864:
1859:
1855:
1851:
1848:
1844:
1839:
1834:
1831:
1790:
1764:
1741:
1723:
1720:
1717:
1714:
1711:
1706:
1702:
1698:
1695:
1692:
1689:
1686:
1681:
1676:
1673:
1670:
1666:
1662:
1659:
1656:
1653:
1648:
1644:
1640:
1637:
1632:
1627:
1624:
1621:
1617:
1604:
1601:
1567:
1536:
1482:
1479:
1476:
1358:
1345:
1319:
1312:
1305:
1284:
1263:
1260:
1257:
1254:
1236:
1232:
1228:
1223:i = i + 1
1220:
1204:
1147:of two nodes,
1090:Main article:
1087:
1084:
1062:
1059:
1024:
1021:
1019:
1016:
998:
995:
975:Raimund Seidel
948:linear probing
907:
904:
855:
852:
836:
833:
831:
828:
774:
771:
704:
701:
698:
695:
670:
666:
662:
658:
654:
651:
648:
645:
642:
639:
635:
629:
626:
623:
620:
616:
613:
603:
474:
453:
450:
447:
444:
433:
432:
421:
418:
411:
407:
403:
396:
391:
388:
385:
381:
375:
372:
369:
365:
279:
240:: An array of
219:
216:
194:, for example
159:
158:
156:
155:
148:
141:
133:
130:
129:
128:
127:
122:
114:
113:
109:
108:
107:
106:
101:
96:
88:
87:
81:
80:
79:
78:
73:
68:
63:
58:
50:
49:
39:
38:
26:
9:
6:
4:
3:
2:
4462:
4451:
4448:
4446:
4443:
4442:
4440:
4425:
4422:
4420:
4417:
4416:
4413:
4407:
4404:
4402:
4399:
4397:
4394:
4392:
4389:
4387:
4384:
4382:
4379:
4377:
4374:
4372:
4369:
4367:
4364:
4362:
4359:
4357:
4356:Hash function
4354:
4352:
4349:
4347:
4344:
4342:
4339:
4337:
4334:
4332:
4329:
4327:
4324:
4322:
4319:
4317:
4314:
4312:
4311:Binary search
4309:
4307:
4304:
4303:
4301:
4297:
4291:
4288:
4286:
4283:
4281:
4278:
4276:
4273:
4271:
4268:
4266:
4263:
4261:
4258:
4256:
4253:
4251:
4248:
4246:
4243:
4241:
4238:
4236:
4233:
4231:
4228:
4226:
4223:
4222:
4220:
4216:
4212:
4208:
4201:
4196:
4194:
4189:
4187:
4182:
4181:
4178:
4174:
4169:
4166:
4163:
4159:
4154:
4149:
4145:
4141:
4137:
4132:
4128:
4122:
4118:
4114:
4110:
4107:
4103:
4100:
4096:
4093:
4090:
4086:
4082:
4079:
4075:
4071:
4067:
4063:
4058:
4055:
4051:
4047:
4046:Jon Kleinberg
4044:
4041:
4039:
4033:
4030:
4029:0-262-03293-7
4026:
4022:
4021:
4016:
4012:
4008:
4004:
4001:
4000:
3987:
3981:
3977:
3973:
3966:
3965:
3960:
3959:Winfree, Erik
3956:
3955:Salomaa, Arto
3952:
3948:
3944:
3943:Winfree, Erik
3940:
3939:Cook, Matthew
3934:
3927:
3923:
3918:
3913:
3909:
3905:
3901:
3895:
3888:
3884:
3880:
3878:0-89791-193-8
3874:
3870:
3866:
3861:
3856:
3849:
3848:
3843:
3837:
3830:
3826:
3822:
3818:
3814:
3810:
3809:
3801:
3794:
3786:
3784:9780521029834
3780:
3776:
3769:
3761:
3755:
3751:
3744:
3736:
3732:
3727:
3722:
3718:
3714:
3713:
3705:
3698:
3692:
3684:
3680:
3676:
3672:
3667:
3662:
3658:
3654:
3650:
3643:
3636:
3632:
3628:
3622:
3614:
3608:
3600:
3596:
3592:
3586:
3582:
3581:
3573:
3571:
3563:
3562:
3557:
3556:Pugh, William
3552:
3544:
3542:0-8186-1982-1
3538:
3534:
3530:
3526:
3522:
3515:
3507:
3503:
3499:
3495:
3490:
3485:
3481:
3477:
3473:
3466:
3458:
3454:
3449:
3444:
3440:
3436:
3432:
3425:
3417:
3413:
3409:
3405:
3401:
3397:
3393:
3386:
3379:
3378:
3373:
3372:Knuth, Donald
3368:
3360:
3354:
3350:
3349:
3341:
3339:
3337:
3335:
3333:
3331:
3322:
3318:
3314:
3312:9781450377867
3308:
3304:
3300:
3296:
3292:
3285:
3277:
3273:
3269:
3263:
3259:
3255:
3251:
3246:
3242:
3236:
3228:
3224:
3220:
3216:
3212:
3205:
3197:
3193:
3189:
3185:
3181:
3177:
3173:
3166:
3158:
3154:
3150:
3146:
3142:
3138:
3134:
3127:
3120:
3116:
3112:
3111:
3106:
3102:
3097:
3093:
3089:
3083:
3075:
3071:
3067:
3063:
3056:
3048:
3044:
3040:
3036:
3032:
3028:
3021:
3017:
3007:
3004:
3002:
2999:
2997:
2994:
2992:
2989:
2987:
2984:
2982:
2979:
2977:
2974:
2972:
2969:
2967:
2964:
2962:
2959:
2957:
2954:
2952:
2949:
2948:
2939:
2935:
2931:
2928:
2924:
2920:
2916:
2912:
2908:
2904:
2886:
2860:
2857:
2854:
2846:
2842:
2838:
2834:
2830:
2827:
2823:
2819:
2818:
2817:
2815:
2802:
2801:brute-forcing
2798:
2797:hash function
2794:
2791:
2787:
2783:
2779:
2775:
2773:
2769:
2765:
2762:
2759:
2757:
2753:
2749:
2748:
2747:
2744:
2742:
2738:
2734:
2730:
2719:
2716:
2708:
2697:
2694:
2690:
2687:
2683:
2680:
2676:
2673:
2669:
2666: –
2665:
2661:
2660:Find sources:
2654:
2650:
2646:
2640:
2639:
2635:
2630:This section
2628:
2624:
2619:
2618:
2610:
2593:
2590:
2587:
2582:
2578:
2571:
2568:
2562:
2559:
2553:
2531:
2528:
2523:
2520:
2498:
2495:
2490:
2487:
2467:
2464:
2461:
2456:
2449:
2446:
2443:
2437:
2431:
2428:
2406:
2401:
2391:
2388:
2385:
2379:
2375:
2370:
2367:
2363:
2358:
2355:
2329:
2326:
2323:
2317:
2313:
2308:
2302:
2299:
2294:
2290:
2274:
2261:
2257:
2252:
2249:
2244:
2239:
2234:
2231:
2226:
2221:
2216:
2213:
2208:
2204:
2200:
2194:
2191:
2188:
2183:
2180:
2177:
2171:
2166:
2160:
2157:
2154:
2149:
2146:
2143:
2137:
2132:
2127:
2123:
2120:
2117:
2111:
2107:
2101:
2098:
2093:
2089:
2074:
2069:
2052:
2049:
2046:
2041:
2038:
2035:
2032:
2029:
2023:
2017:
2014:
2011:
2007:
2002:
1999:
1996:
1980:
1976:
1969:
1960:
1955:
1952:
1943:
1927:
1923:
1917:
1914:
1911:
1897:
1891:
1887:
1857:
1853:
1846:
1837:
1832:
1829:
1821:
1817:
1813:
1809:
1804:
1800:
1793:
1789:
1782:
1778:
1773:
1767:
1763:
1758:
1754:
1749:
1744:
1740:
1734:
1721:
1712:
1709:
1704:
1700:
1690:
1687:
1679:
1674:
1671:
1668:
1664:
1660:
1654:
1651:
1646:
1642:
1630:
1625:
1622:
1619:
1615:
1599:
1596:
1591:
1587:
1583:
1579:
1575:
1565:
1563:
1560:has at least
1559:
1555:
1551:
1547:
1534:
1532:
1528:
1524:
1520:
1516:
1512:
1508:
1504:
1480:
1477:
1474:
1462:
1458:
1455:. Initially,
1454:
1450:
1446:
1442:
1437:
1433:
1429:
1425:
1421:
1417:
1413:
1409:
1405:
1400:
1395:
1391:
1387:
1382:
1378:
1374:
1370:
1366:
1356:
1353:
1348:
1344:
1338:
1334:
1329:
1322:
1318:
1311:
1304:
1300:
1295:
1283:
1281:
1277:
1258:
1252:
1242:
1226:
1218:
1214:
1211:
1207:
1203:
1196:
1188:
1184:
1182:
1178:
1174:
1170:
1166:
1162:
1158:
1154:
1150:
1146:
1141:
1139:
1135:
1131:
1127:
1123:
1119:
1115:
1113:
1109:
1105:
1102:
1098:
1093:
1083:
1081:
1076:
1072:
1068:
1058:
1056:
1052:
1048:
1043:
1039:
1035:
1034:
1029:
1015:
1012:
1008:
1004:
994:
992:
988:
984:
980:
976:
972:
967:
965:
960:
957:
953:
952:Andrey Ershov
949:
945:
941:
940:Arthur Samuel
937:
933:
929:
925:
921:
917:
913:
903:
901:
897:
893:
889:
885:
881:
877:
873:
869:
865:
861:
854:Number theory
851:
849:
845:
841:
830:Early history
827:
825:
821:
816:
814:
810:
805:
801:
797:
793:
789:
785:
784:
779:
770:
768:
764:
760:
756:
751:
749:
745:
741:
737:
733:
729:
725:
721:
716:
699:
683:
668:
660:
656:
652:
646:
643:
640:
602:
600:
596:
592:
472:
469:
467:
448:
419:
416:
409:
405:
401:
394:
389:
386:
383:
379:
367:
355:
354:
353:
277:
274:
272:
268:
263:
261:
257:
253:
251:
247:
243:
239:
235:
233:
229:
225:
215:
212:
207:
205:
201:
197:
193:
188:
185:
181:
177:
173:
166:
154:
149:
147:
142:
140:
135:
134:
132:
131:
126:
123:
121:
118:
117:
116:
115:
111:
110:
105:
102:
100:
97:
95:
92:
91:
90:
89:
86:
83:
82:
77:
74:
72:
69:
67:
64:
62:
59:
57:
54:
53:
52:
51:
48:
44:
43:Probabilistic
41:
40:
36:
32:
31:
19:
4381:Root-finding
4370:
4306:Backtracking
4270:Segment tree
4240:Fenwick tree
4172:
4161:
4143:
4139:
4116:
4098:
4088:
4065:
4061:
4053:
4037:
4018:
3963:
3951:Harel, David
3947:Condon, Anne
3933:
3907:
3903:
3894:
3846:
3836:
3812:
3806:
3793:
3774:
3768:
3752:, Springer,
3749:
3743:
3716:
3710:
3704:
3691:
3656:
3652:
3642:
3635:Zentralblatt
3634:
3630:
3626:
3621:
3579:
3559:
3551:
3524:
3514:
3479:
3475:
3465:
3438:
3434:
3424:
3399:
3395:
3385:
3375:
3367:
3347:
3294:
3284:
3248:
3235:
3218:
3214:
3204:
3179:
3175:
3165:
3140:
3136:
3126:
3108:
3082:
3065:
3061:
3055:
3030:
3026:
3020:
2825:
2811:
2790:pseudorandom
2785:
2745:
2728:
2726:
2711:
2702:
2692:
2685:
2678:
2671:
2659:
2643:Please help
2631:
2275:
2072:
2070:
1944:
1895:
1889:
1885:
1883:. Note that
1819:
1815:
1811:
1802:
1798:
1791:
1787:
1780:
1779:∈ {0, 1, …,
1776:
1771:
1765:
1761:
1756:
1752:
1747:
1742:
1738:
1735:
1606:
1594:
1589:
1585:
1581:
1577:
1573:
1571:
1561:
1557:
1553:
1549:
1545:
1537:
1530:
1526:
1522:
1518:
1514:
1510:
1506:
1464:
1460:
1456:
1452:
1448:
1444:
1440:
1435:
1431:
1427:
1423:
1419:
1415:
1411:
1407:
1403:
1398:
1393:
1389:
1385:
1380:
1376:
1372:
1368:
1364:
1362:
1351:
1346:
1342:
1336:
1332:
1327:
1320:
1316:
1309:
1302:
1298:
1293:
1285:
1279:
1275:
1244:
1240:
1224:
1216:
1212:
1209:
1205:
1201:
1180:
1176:
1172:
1168:
1164:
1160:
1156:
1152:
1148:
1142:
1137:
1133:
1129:
1125:
1117:
1116:
1111:
1107:
1103:
1096:
1095:
1064:
1054:
1050:
1046:
1041:
1037:
1031:
1026:
1000:
987:William Pugh
971:Bloom filter
968:
961:
956:Donald Knuth
944:IBM Research
924:linked lists
909:
868:square roots
857:
838:
817:
781:
776:
762:
758:
752:
740:cryptography
717:
685:
604:
598:
594:
590:
588:
470:
434:
351:
275:
264:
259:
255:
254:
249:
245:
241:
237:
236:
231:
223:
221:
208:
189:
171:
169:
119:
85:Random trees
61:Count sketch
56:Bloom filter
42:
4260:Linked list
4146:: 128–138.
3815:(1): 1–17,
3119:section 1.2
3101:Hal Abelson
3092:Fermat test
3068:: 235–246.
3033:(7): 321–.
3027:Commun. ACM
2971:HyperLogLog
2776:the use of
1401:induced by
1145:contraction
1071:convex hull
973:. In 1989,
950:, although
946:introduced
928:Gene Amdahl
575:'a'
476:findingA_MC
338:'a'
281:findingA_LV
258:: Find an ‘
125:HyperLogLog
4439:Categories
4396:Sweep line
4371:Randomized
4299:Algorithms
4250:Hash table
4211:algorithms
4050:Éva Tardos
3997:References
3900:Shamir, A.
3842:Füredi, Z.
3695:Seidel R.
3143:(7): 321.
2782:dispersers
2675:newspapers
2546:, in time
1814:is not in
1564:/2 edges.
1330:, no edge
1208:i = 1
1003:Paul Erdős
912:hash table
844:Tony Hoare
736:randomness
234:elements.
218:Motivation
180:randomness
4391:Streaming
4376:Recursion
3855:CiteSeerX
3721:CiteSeerX
3683:122784453
3675:0008-414X
3659:: 34–38.
3607:cite book
3599:910535517
3498:0001-0782
3457:0022-0000
3416:0036-1399
3196:0001-0782
3157:0001-0782
3115:MIT Press
3047:0001-0782
2881:Θ
2858:
2632:does not
2591:
2524:−
2491:−
2465:
2447:−
2389:−
2371:−
2359:−
2327:−
2309:≥
2205:…
2192:−
2181:−
2158:−
2147:−
2121:−
2108:≥
2050:−
2039:−
2033:−
2015:−
2003:−
1997:≥
1956:−
1915:−
1833:−
1691:−
1665:∏
1652:≠
1616:∏
1478:≠
1028:Quicksort
1023:Quicksort
991:skip list
888:primality
858:In 1917,
840:Quicksort
788:Las Vegas
694:Θ
647:−
443:Θ
380:∑
374:∞
371:→
196:Quicksort
176:algorithm
76:Skip list
4115:(1993),
4085:E. Upfal
3961:(eds.),
3887:17867291
3829:13268711
3633:8,479d;
3374:(1963),
3107:(1996).
2961:Bogosort
2945:See also
2770:used in
2729:removing
1422: :
1406: :
1235:, ..., C
1018:Examples
786:. Both
720:attacker
539:elements
518:Randomly
329:elements
308:Randomly
269:and one
226:’ in an
35:a series
33:Part of
4386:Sorting
4361:Minimax
3637:32,192.
3506:7931252
3321:6464612
3276:1314885
2786:amplify
2689:scholar
2653:removed
2638:sources
1942:edges.
1556:, then
1539:Lemma 2
1493:
1467:
1315:, ...,
1287:Lemma 1
1086:Min cut
835:Sorting
589:If an ‘
527:element
464:. (See
317:element
112:Related
4366:Online
4351:Greedy
4280:String
4123:
4027:
4013:, and
3982:
3926:315182
3924:
3885:
3875:
3857:
3827:
3781:
3756:
3723:
3681:
3673:
3597:
3587:
3539:
3504:
3496:
3455:
3414:
3355:
3319:
3309:
3274:
3264:
3194:
3155:
3045:
2923:PSPACE
2911:Füredi
2907:Bárány
2691:
2684:
2677:
2670:
2662:
2421:. For
1945:Thus,
1274:, and
1213:repeat
1210:repeat
1118:Output
938:, and
631:
601:’ is:
521:select
515:repeat
311:select
305:repeat
256:Output
174:is an
4275:Stack
4265:Queue
4245:Graph
4225:Array
3968:(PDF)
3922:S2CID
3883:S2CID
3851:(PDF)
3825:S2CID
3803:(PDF)
3679:S2CID
3502:S2CID
3317:S2CID
3012:Notes
2932:In a
2696:JSTOR
2682:books
1569:Proof
1451:} of
1410:= { {
1360:Proof
1225:until
1217:until
1206:begin
1101:graph
1097:Input
1011:Erdős
983:treap
581:found
560:until
503:begin
482:array
344:found
335:until
302:begin
287:array
238:Input
228:array
99:Treap
4346:Fold
4290:Trie
4285:Tree
4255:Heap
4209:and
4121:ISBN
4083:and
4048:and
4025:ISBN
3980:ISBN
3873:ISBN
3779:ISBN
3754:ISBN
3671:ISSN
3613:link
3595:OCLC
3585:ISBN
3537:ISBN
3494:ISSN
3453:ISSN
3412:ISSN
3353:ISBN
3307:ISBN
3262:ISBN
3250:1993
3192:ISSN
3153:ISSN
3103:and
3086:"In
3043:ISSN
2914:box.
2909:and
2780:(or
2750:the
2668:news
2636:any
2634:cite
1796:has
1783:− 3}
1584:) ≥
1517:= {(
1499:and
1418:} ∈
1375:and
1292:Let
1179:and
1171:and
1151:and
1136:and
1128:and
1120:: A
1099:: A
977:and
878:and
790:and
726:and
252:’s.
204:MFAS
4148:doi
4070:doi
3972:doi
3912:doi
3865:doi
3817:doi
3731:doi
3661:doi
3529:doi
3484:doi
3443:doi
3404:doi
3299:doi
3254:doi
3223:doi
3184:doi
3145:doi
3070:doi
3035:doi
2855:log
2843:In
2835:or
2741:BPP
2647:by
2588:log
2075:is
1544:If
1363:If
1335:∈
1301:= {
1241:end
1231:, C
1163:or
1122:cut
1073:or
1065:In
942:of
920:IBM
918:at
820:BPP
813:ZPP
584:end
530:out
524:one
364:lim
347:end
320:out
314:one
230:of
4441::
4144:12
4142:.
4138:.
4087:.
4066:51
4064:.
4052:.
4017:.
4009:,
4005:,
3978:,
3957:;
3949:;
3920:,
3908:39
3906:,
3881:,
3871:,
3863:,
3823:,
3813:38
3811:,
3805:,
3729:.
3717:24
3715:.
3677:.
3669:.
3657:11
3655:.
3651:.
3631:MR
3627:53
3609:}}
3605:{{
3593:.
3569:^
3535:.
3523:.
3500:.
3492:.
3480:13
3478:.
3474:.
3451:.
3439:18
3437:.
3433:.
3410:.
3400:14
3398:.
3394:.
3329:^
3315:.
3305:.
3293:.
3272:MR
3270:,
3260:,
3243:;
3217:.
3213:.
3190:.
3178:.
3174:.
3151:.
3139:.
3135:.
3117:,
3113:.
3066:41
3064:.
3041:.
3029:.
2927:NP
2919:IP
2739:=
2609:.
2462:ln
2284:Pr
2083:Pr
2068:.
1801:−
1785:.
1746:=
1694:Pr
1636:Pr
1590:pk
1562:pk
1495:,
1434:∈
1426:∈
1355:.
1350:=
1308:,
1239:.
1140:.
1114:)
1082:.
1009:.
993:.
934:,
930:,
815:.
800:RP
750:.
715:.
612:Pr
578:is
572:or
548::=
533:of
509::=
468:)
341:is
323:of
273:.
170:A
37:on
4199:e
4192:t
4185:v
4156:.
4150::
4076:.
4072::
4040:"
4036:"
3989:.
3974::
3914::
3867::
3819::
3763:.
3737:.
3733::
3699:.
3685:.
3663::
3615:)
3601:.
3545:.
3531::
3508:.
3486::
3459:.
3445::
3418:.
3406::
3361:.
3323:.
3301::
3256::
3229:.
3225::
3219:7
3198:.
3186::
3180:4
3159:.
3147::
3141:4
3121:.
3076:.
3072::
3049:.
3037::
3031:4
2940:.
2929:.
2890:)
2887:n
2884:(
2861:n
2826:a
2737:P
2718:)
2712:(
2707:)
2703:(
2693:·
2686:·
2679:·
2672:·
2655:.
2641:.
2597:)
2594:n
2583:3
2579:n
2575:(
2572:O
2569:=
2566:)
2563:n
2560:m
2557:(
2554:O
2532:n
2529:1
2521:1
2499:n
2496:1
2488:1
2468:n
2457:2
2453:)
2450:1
2444:n
2441:(
2438:n
2432:=
2429:m
2407:m
2402:)
2395:)
2392:1
2386:n
2383:(
2380:n
2376:2
2368:1
2364:(
2356:1
2333:)
2330:1
2324:n
2321:(
2318:n
2314:2
2306:]
2303:C
2300:=
2295:i
2291:C
2287:[
2262:.
2258:)
2253:3
2250:1
2245:(
2240:)
2235:4
2232:2
2227:(
2222:)
2217:5
2214:3
2209:(
2201:)
2195:2
2189:n
2184:4
2178:n
2172:(
2167:)
2161:1
2155:n
2150:3
2144:n
2138:(
2133:)
2128:n
2124:2
2118:n
2112:(
2105:]
2102:C
2099:=
2094:i
2090:C
2086:[
2073:C
2053:j
2047:n
2042:2
2036:j
2030:n
2024:=
2018:j
2012:n
2008:2
2000:1
1990:|
1986:)
1981:j
1977:G
1973:(
1970:E
1966:|
1961:k
1953:1
1928:2
1924:k
1921:)
1918:j
1912:n
1909:(
1896:k
1890:j
1886:G
1867:|
1863:)
1858:j
1854:G
1850:(
1847:E
1843:|
1838:k
1830:1
1820:C
1816:C
1812:j
1803:j
1799:n
1792:j
1788:G
1781:n
1777:j
1772:j
1766:j
1762:G
1757:i
1753:C
1748:C
1743:i
1739:C
1722:.
1719:)
1716:)
1713:C
1710:=
1705:i
1701:C
1697:(
1688:1
1685:(
1680:m
1675:1
1672:=
1669:i
1661:=
1658:)
1655:C
1647:i
1643:C
1639:(
1631:m
1626:1
1623:=
1620:i
1595:E
1586:k
1582:v
1578:v
1574:k
1558:G
1554:k
1550:p
1546:G
1531:B
1529:,
1527:A
1523:B
1521:,
1519:A
1515:C
1511:R
1507:L
1501:v
1497:u
1481:e
1475:f
1461:v
1459:,
1457:u
1453:C
1449:v
1447:,
1445:u
1441:G
1436:R
1432:v
1430:,
1428:L
1424:u
1420:E
1416:v
1414:,
1412:u
1408:C
1404:C
1399:V
1394:R
1392:∪
1390:L
1388:=
1386:V
1381:G
1377:R
1373:L
1369:G
1365:G
1352:C
1347:i
1343:C
1337:C
1333:e
1328:i
1324:}
1321:k
1317:e
1313:2
1310:e
1306:1
1303:e
1299:C
1294:k
1280:m
1276:n
1262:)
1259:n
1256:(
1253:O
1237:m
1233:2
1229:1
1221:i
1181:B
1177:A
1173:v
1169:u
1165:v
1161:u
1157:u
1153:v
1149:u
1138:R
1134:L
1130:R
1126:L
1112:E
1110:,
1108:V
1106:(
1104:G
1055:n
1051:n
1049:(
1047:O
1042:n
1038:n
1036:(
1033:O
824:P
759:k
703:)
700:1
697:(
669:k
665:)
661:2
657:/
653:1
650:(
644:1
641:=
638:]
634:a
628:d
625:n
622:i
619:f
615:[
599:a
595:k
591:a
569:k
566:=
563:i
557:1
554:+
551:i
545:i
542:.
536:n
512:0
506:i
500:)
497:k
494:,
491:n
488:,
485:A
479:(
452:)
449:1
446:(
420:2
417:=
410:i
406:2
402:i
395:n
390:1
387:=
384:i
368:n
332:.
326:n
299:)
296:n
293:,
290:A
284:(
260:a
250:b
246:a
242:n
232:n
224:a
167:.
152:e
145:t
138:v
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.