{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T17:23:00Z","timestamp":1649092980411},"reference-count":108,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1984,10,1]],"date-time":"1984-10-01T00:00:00Z","timestamp":465436800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[1984,10]]},"DOI":"10.1007\/bf01874396","type":"journal-article","created":{"date-parts":[[2005,7,2]],"date-time":"2005-07-02T18:31:47Z","timestamp":1120329107000},"page":"331-345","source":"Crossref","is-referenced-by-count":3,"title":["Randomized algorithms: An annotated bibliography"],"prefix":"10.1007","volume":"1","author":[{"given":"E.","family":"Maffioli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. G.","family":"Speranza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C.","family":"Vercellis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF01874396_CR1","unstructured":"L. Adleman, Two theorems on random polynomial time, Proc. 19th Symp. Found. Comp. Sc. (1980) p. 75."},{"key":"BF01874396_CR2","doi-asserted-by":"crossref","unstructured":"L. Adleman, On distinguishing prime numbers from composite numbers, Proc. 21st Symp. Found. Comp. Sc. (1980) p. 387.","DOI":"10.1109\/SFCS.1980.28"},{"key":"BF01874396_CR3","unstructured":"L. Adleman and K. Manders, Reducibility, randomness and intractability, Proc. 9th ACM Symp Theory Comput. (1977) p. 151."},{"key":"BF01874396_CR4","unstructured":"R. Aleliunas, R. Karp, R. Lipton, L. Lov\u00e1sz and C. Rackoff, Random walks, universal sequences and the complexity of maze problems, Proc. 20th Found. Comp. Sc. (1979) p. 218."},{"key":"BF01874396_CR5","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0022-0000(79)90045-X","volume":"18","author":"D. Angluin","year":"1979","unstructured":"D. Angluin and L.G. Valiant, Fast probabilistic algorithms for hamiltonian circuits and matchings, J. Comp. and Syst. Sc. 18(1979) 155.","journal-title":"J. Comp. and Syst. Sc."},{"key":"BF01874396_CR6","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1137\/0211064","volume":"11","author":"A.O.L. Atkin","year":"1982","unstructured":"A.O.L. Atkin and R.G. Larson, On a primality test of Solovay and Strassen, SIAM J. Comput. 11(1982) 789.","journal-title":"SIAM J. Comput."},{"key":"BF01874396_CR7","unstructured":"L. Babai, Monte-Carlo algorithms in graph isomorphism testing, Rapports de Recherches du Departement de Mathematiques et de Statistique, D.M.S., Nr. 79-10, C.P. 6128, Succ. A\u2032 (Montreal, Quebec H3C 3J7, 1979)."},{"key":"BF01874396_CR8","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/0204037","volume":"4","author":"T. Baker","year":"1975","unstructured":"T. Baker, J. Gill and R. Solovay, Relativization of theP\u225fNP question, SIAM J. Comput 4(1975) 431.","journal-title":"SIAM J. Comput"},{"key":"BF01874396_CR9","first-page":"967","volume":"191","author":"J.M. Barzdin","year":"1970","unstructured":"J.M. Barzdin, On the frequency solution of algorithmically unsolvable mass problems, Dokl. Akad. Nauk. SSSR 191(1970) 967.","journal-title":"Dokl. Akad. Nauk. SSSR"},{"key":"BF01874396_CR10","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0020-0190(82)90046-1","volume":"15","author":"M. Becker","year":"1982","unstructured":"M. Becker, W. Degenhardt, J. Doenhardt, S. Hertel, G. Kaninke, W. Weber, K. Mehlhorn, S. Naher, H. Rohnert and T. Winter, A probabilistic algorithm for vertex connectivity of graphs, Inf. Proc. Lett. 15(1982) 135.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR11","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"C.H. Bennett and J. Gill, Relative to a random oracleA, P A \u2260NP A \u2260 co -NP A with probability 1, SIAM J. Comput. 10(1981) 96.","journal-title":"SIAM J. Comput."},{"key":"BF01874396_CR12","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","volume":"24","author":"E.R. Berlekamp","year":"1970","unstructured":"E.R. Berlekamp, Factoring polynomials over large finite fields, Math. Comput. 24(1970) 713.","journal-title":"Math. Comput."},{"key":"BF01874396_CR13","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1016\/S0020-0190(80)90078-2","volume":"10","author":"M. Blum","year":"1980","unstructured":"M. Blum, A.K. Chandra and M.N. Wegman, Equivalence of free boolean graphs can be decided probabilistically in polynomial time, Inf. Proc. Lett. 10(1980) 80.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR14","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1016\/0020-0190(80)90011-3","volume":"11","author":"J. Calmet","year":"1980","unstructured":"J. Calmet and R. Loos, An improvement of Rabin's probabilistic algorithm for generating irreducible polynomials overGF(p), Inf. Proc. Lett. 11(1980) 94.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR15","unstructured":"J.L. Carter and M.N. Wegman, Universal classes of hash functions, Proc. 9th ACM Symp. Theory Comput. (1977) p. 106."},{"key":"BF01874396_CR16","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1147\/rd.214.0350","volume":"21","author":"G.J. Chaitin","year":"1977","unstructured":"G.J. Chaitin, Algorithmic information theory. IBM J. Res. Develop. 21(1977) 350.","journal-title":"IBM J. Res. Develop."},{"key":"BF01874396_CR17","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1002\/cpa.3160310407","volume":"31","author":"G.J. Chaitin","year":"1978","unstructured":"G.J. Chaitin and J.T. Schwartz, A note on Monte-Carlo primality tests and algorithmic information theory. Commun. Pure Appl. Math. 31(1978) 521.","journal-title":"Commun. Pure Appl. Math."},{"key":"BF01874396_CR18","doi-asserted-by":"crossref","first-page":"1273","DOI":"10.1287\/mnsc.23.12.1273","volume":"23","author":"D.G. Dannenbring","year":"1977","unstructured":"D.G. Dannenbring, Procedures for estimating optimal solution values for large combinatorial problems, Manag. Sci. 23(1977) 1273.","journal-title":"Manag. Sci."},{"key":"BF01874396_CR19","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1145\/322003.322013","volume":"24","author":"P.J. Davis","year":"1977","unstructured":"P.J. Davis, Proof, completeness, transcendentals and sampling, J. ACM 24(1977) 298.","journal-title":"J. ACM"},{"key":"BF01874396_CR20","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1016\/0020-0190(79)90085-1","volume":"8","author":"S. Fortune","year":"1979","unstructured":"S. Fortune and J. Hopcroft, A note on Rabin's nearest neighbor algorithm, Inf. Proc. Lett. 8(1979) 20.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR21","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1145\/321592.321600","volume":"17","author":"W.D. Frazer","year":"1970","unstructured":"W.D. Frazer and A.C. McKellar, Samplesort: a sampling approach to minimal storage tree sorting. J. ACM 17(1970) 496.","journal-title":"J. ACM"},{"key":"BF01874396_CR22","doi-asserted-by":"crossref","unstructured":"M.L. Freedman, Two applications of a probabilistic search technique: sortingx+y and building balanced search trees, Proc. 7th ACM Symp. Theory Comput. (1975) p. 240.","DOI":"10.1145\/800116.803774"},{"key":"BF01874396_CR23","series-title":"Inf. Proc.","first-page":"839","volume-title":"Probabilistic machines can use less running time","author":"R. Freivalds","year":"1977","unstructured":"R. Freivalds, Probabilistic machines can use less running time, Inf. Proc. 77, ed. B. Gilchrist (North-Holland, Amsterdam, 1977) p. 839."},{"key":"BF01874396_CR24","first-page":"295","volume":"19","author":"R. Freivalds","year":"1978","unstructured":"R. Freivalds, Recognition of languages with high probability of different classes of automata, Soviet Math. Dokl. 19(1978) 295.","journal-title":"Soviet Math. Dokl."},{"key":"BF01874396_CR25","series-title":"Math. Found. Comp. Sci.","first-page":"57","volume-title":"Fast probabilistic algorithms","author":"R. Freivalds","year":"1979","unstructured":"R. Freivalds, Fast probabilistic algorithms, Math. Found. Comp. Sci. (Springer, Berlin, 1979) p. 57."},{"key":"BF01874396_CR26","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0020-0190(81)90057-0","volume":"13","author":"R. Freivalds","year":"1981","unstructured":"R. Freivalds, Projections of languages recognizable by probabilistic and alternating finite multitape automata, Inf. Proc. Lett. 13(1981) 195.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR27","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/3-540-10856-4_72","volume":"118","author":"R. Freivalds","year":"1981","unstructured":"R. Freivalds, Probabilistic two-way machines, Lecture Notes in Comp. Sci. 118(1981) 33.","journal-title":"Lecture Notes in Comp. Sci."},{"key":"BF01874396_CR28","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J.T. Gill","year":"1977","unstructured":"J.T. Gill, Computational complexity of probabilistic Turing machines, SIAM J. Comput. 6(1977) 675.","journal-title":"SIAM J. Comput."},{"key":"BF01874396_CR29","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1002\/net.3230070303","volume":"7","author":"B.L. Golden","year":"1977","unstructured":"B.L. Golden, A statistical approach to the TSP, Networks 7(1977) 209.","journal-title":"Networks"},{"key":"BF01874396_CR30","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1002\/nav.3800260108","volume":"26","author":"B.L. Golden","year":"1979","unstructured":"B.L. Golden and F.B. Alt, Interval estimation of a global optimum for large combinatorial problems, Nav. Res. Log. Quart. 26(1979) 69.","journal-title":"Nav. Res. Log. Quart."},{"key":"BF01874396_CR31","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1017\/S0305004100051124","volume":"77","author":"G.R. Grimmett","year":"1975","unstructured":"G.R. Grimmett and C.J.H. McDiarmid, On colouring random graphs, Math. Proc. Camb. Phil. Soc. 77(1975) 313.","journal-title":"Math. Proc. Camb. Phil. Soc."},{"key":"BF01874396_CR32","series-title":"Lecture, Notes Comp. Sci.","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1007\/3-540-10843-2_2","volume-title":"Absolute primality of polynomials is decidable in random polynomial time in the number of, variables","author":"J. Heintz","year":"1981","unstructured":"J. Heintz and M. Sieveking, Absolute primality of polynomials is decidable in random polynomial time in the number of, variables, Lecture, Notes Comp. Sci. 115 (Springer, Berlin, 1981) p. 16."},{"key":"BF01874396_CR33","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1007\/BF01933646","volume":"20","author":"T. Herlestam","year":"1980","unstructured":"T. Herlestam, A note on Rabin's probabilistic primality test, BIT 20(1980) 518.","journal-title":"BIT"},{"key":"BF01874396_CR34","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1093\/comjnl\/5.1.10","volume":"5","author":"C.A.R. Hoare","year":"1962","unstructured":"C.A.R. Hoare, Quicksort, Comput. J. 5(1962) 10.","journal-title":"Comput. J."},{"key":"BF01874396_CR35","series-title":"Proc. 5th Conf. Theor. Comp. Sci.","first-page":"123","volume-title":"Recent directions in algorithmic research","author":"J. Hopcroft","year":"1981","unstructured":"J. Hopcroft, Recent directions in algorithmic research, Proc. 5th Conf. Theor. Comp. Sci., ed. P. Deussen (Springer, Berlin, 1981) p. 123."},{"key":"BF01874396_CR36","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/0020-0190(81)90142-3","volume":"13","author":"O.H. Ibarra","year":"1981","unstructured":"O.H. Ibarra and S. Moran, Determinstic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication, Inf. Proc. Lett. 13(1981) 12.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR37","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1145\/322358.322373","volume":"30","author":"O.H. Ibarra","year":"1983","unstructured":"O.H. Ibarra and S. Moran, Probabilistic algorithms for deciding equivalence of straight line programs, J. ACM 30(1983) 217.","journal-title":"J. ACM"},{"key":"BF01874396_CR38","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0020-0190(81)90019-3","volume":"12","author":"O.H. Ibarra","year":"1981","unstructured":"O.H. Ibarra, L. Roster and S. Moran, Probabilistic algorithms and straight line programs for some rank decision problems, Inf. Proc. Lett. 12(1981) 227.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR39","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1016\/0020-0190(79)90051-6","volume":"9","author":"A. Itai","year":"1979","unstructured":"A. Itai, A randomized algorithm for checking equivalence of circular lists, Inf. Proc. Lett. 9(1979) 118.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR40","series-title":"Springer Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/3-540-08860-1_21","volume-title":"Covering a graph by circuits","author":"A. Itai","year":"1978","unstructured":"A. Itai and M. Rodeh, Covering a graph by circuits, Springer Lect. Notes Comput. Sci. 62 (Springer-Verlag, Berlin, 1978) p. 289."},{"key":"BF01874396_CR41","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1145\/355681.355685","volume":"2","author":"W. Janko","year":"1976","unstructured":"W. Janko, A list insertion sort for keys with arbitrary key distribution, ACM Trans. Math. Soft. 2(1976) 143.","journal-title":"ACM Trans. Math. Soft."},{"key":"BF01874396_CR42","first-page":"373","volume-title":"Proc. Int. Comput. Symp.","author":"W. Janko","year":"1977","unstructured":"W. Janko, An insertion sort for uniformly distributed keys based on stopping theory, Proc. Int. Comput. Symp., ed. E. Horlet and D. Ribbens (North-Holland, Amsterdam, 1977) p. 373."},{"key":"BF01874396_CR43","first-page":"165","volume":"36","author":"W. Janko","year":"1980","unstructured":"W. Janko, Probabilistic algorithms and the efficient use of statistical models of decision in their design, Math. Oper. Res. 36(1980) 165.","journal-title":"Math. Oper. Res."},{"key":"BF01874396_CR44","series-title":"Math. Found. Comp. Sci.","first-page":"339","volume-title":"Relationships between probabilistic and deterministic tape complexity","author":"H. Jung","year":"1981","unstructured":"H. Jung, Relationships between probabilistic and deterministic tape complexity, Math. Found. Comp. Sci. (Springer, Berlin, 1981) p. 339."},{"key":"BF01874396_CR45","first-page":"1","volume-title":"The probabilistic analysis of some combinatorial search algorithms, Algorithms and Complexity","author":"R.M. Karp","year":"1976","unstructured":"R.M. Karp, The probabilistic analysis of some combinatorial search algorithms, Algorithms and Complexity, ed. J.F. Traub (Academic Press, New York, 1976) p. 1."},{"key":"BF01874396_CR46","unstructured":"R.M. Karp and R. Lipton, Some connections between non-uniformal and uniformal complexity classes, Proc. 12th ACM Symp. on Theory of Comput (1980) p. 302."},{"key":"BF01874396_CR47","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0020-0190(82)90139-9","volume":"14","author":"Ker-I Ko","year":"1982","unstructured":"Ker-I Ko, Some observations on the probabilistic algorithms and NP-hard problems, Inf. Proc. Lett. 14(1982) 39.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR48","doi-asserted-by":"crossref","unstructured":"D. Kozen, Semantics of probabilistic programs, Proc. 20th Symp. Found. Comput. Sci. (1979) p. 104.","DOI":"10.1109\/SFCS.1979.38"},{"key":"BF01874396_CR49","doi-asserted-by":"crossref","unstructured":"S.L. Kurtz, On the random oracle hypothesis, Proc. 14th ACM Symp. Theory Comput. (1982) p. 224.","DOI":"10.1145\/800070.802195"},{"key":"BF01874396_CR50","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1145\/321864.321877","volume":"22","author":"R. Ladner","year":"1975","unstructured":"R. Ladner, On the structure of polynomial time reducibility, J. ACM 22(1975) 155.","journal-title":"J. ACM"},{"key":"BF01874396_CR51","unstructured":"C. Lardinois, Methodes statistiques en optimisation combinatoire, Res. Rep. Nr. 116 (Universit\u00e9 de Montreal, Centre de Recherche sur les transports, 1979)."},{"key":"BF01874396_CR52","series-title":"Automata Studies","first-page":"183","volume-title":"Computability by probabilistic machines","author":"K. Leeuw de","year":"1955","unstructured":"K. de Leeuw, E.F. Moore, C.E. Shannon and N. Shapiro, Computability by probabilistic machines, Automata Studies, ed. C.E. Shannon and J. McCarthy (Princeton University Press, Princeton, 1955) p. 183."},{"key":"BF01874396_CR53","doi-asserted-by":"crossref","first-page":"374","DOI":"10.1137\/0211029","volume":"11","author":"D.L. Lehmann","year":"1982","unstructured":"D.L. Lehmann, On primality tests, SIAM J. Comput. 11(1982)374.","journal-title":"SIAM J. Comput."},{"key":"BF01874396_CR54","unstructured":"D.L. Lehmann and M.O. Rabin, On the advantage of free choice: a symmetric and fully distributed solution to the dining philosophers problems, Proc. 8th ACM Symp. Princ. Progr. Lang. (1981) p. 133."},{"key":"BF01874396_CR55","unstructured":"T. Leighton and M. Lepley, Probabilistic searching in sorted linked lists, Proc. 20th Allerton Conf. Comm. Contr. Comput. (1982) p. 500."},{"key":"BF01874396_CR56","first-page":"2245","volume":"44","author":"S. Lin","year":"1965","unstructured":"S. Lin, Computer solutions of the traveling salesman problem, B.S.T.J. 44(1965)2245.","journal-title":"B.S.T.J."},{"key":"BF01874396_CR57","unstructured":"L. Lov\u00e1sz, On determinants, matchings and random algorithms, unpublished memo."},{"key":"BF01874396_CR58","series-title":"Proc. 13th Symp. Interface","first-page":"68","volume-title":"Algorithms with random input","author":"G.S. Lueker","year":"1981","unstructured":"G.S. Lueker, Algorithms with random input, Proc. 13th Symp. Interface, ed. W.F. Eddy (Springer Verlag, New York, 1981) p. 68."},{"key":"BF01874396_CR59","unstructured":"F. Maffioli, Couplages et matroides, in: Regards sur la th\u00e9orie des graphes, ed. P. Hansen and D. de Werra (Presses Polytechniques Romandes, 1980) p. 97."},{"key":"BF01874396_CR60","doi-asserted-by":"crossref","first-page":"1331","DOI":"10.1287\/opre.19.6.1331","volume":"19","author":"K.L. McRoberts","year":"1971","unstructured":"K.L. McRoberts, A search model for evaluating combinatorially explosive problems, Oper. Res. 19(1971)1331.","journal-title":"Oper. Res."},{"key":"BF01874396_CR61","unstructured":"K. Mehlhorn and E.M. Schmidt, Las Vegas is better than determinism in VLSI and distributed computing, Proc. 14th ACM Symp. Theory Comput. (1982) p. 330."},{"key":"BF01874396_CR62","doi-asserted-by":"crossref","unstructured":"G.L. Miller, Riemann's hypothesis and tests for primality, Proc. 7th ACM Symp. Theory Comput. (1975) p. 234.","DOI":"10.1145\/800116.803773"},{"key":"BF01874396_CR63","volume-title":"Combinatorial optimization: Algorithms and Complexity","author":"C.H. Papadimitriou","year":"1982","unstructured":"C.H. Papadimitriou and K. Steiglitz, Combinatorial optimization: Algorithms and Complexity (Prentice Hall, Englewood Cliffs, 1982)."},{"key":"BF01874396_CR64","unstructured":"N. Pippenger, Probabilistic simulation, Proc. 14th ACM Symp. Theory Comput. (1982) p. 17."},{"key":"BF01874396_CR65","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF01933667","volume":"15","author":"J.M. Pollard","year":"1975","unstructured":"J.M. Pollard, A Monte-Carlo method for factorization, BIT 15(1975)331.","journal-title":"BIT"},{"key":"BF01874396_CR66","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1016\/0012-365X(76)90068-6","volume":"14","author":"L. Posa","year":"1976","unstructured":"L. Posa, Hamiltonian circuits in random graphs, Discr. Math. 14(1976)359.","journal-title":"Discr. Math."},{"key":"BF01874396_CR67","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"M.O. Rabin","year":"1963","unstructured":"M.O. Rabin, Probabilistic automata, Inf. Control 6(1963)230.","journal-title":"Inf. Control"},{"key":"BF01874396_CR68","first-page":"21","volume-title":"new directions and recent results","author":"M.O. Rabin","year":"1976","unstructured":"M.O. Rabin, Probabilistic algorithms, algorithms and complexity, in: new directions and recent results, ed. J. Traub (Academic Press, New York, 1976) p. 21."},{"key":"BF01874396_CR69","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1145\/359810.359816","volume":"20","author":"M.O. Rabin","year":"1977","unstructured":"M.O. Rabin, Complexity of computations, Commun. ACM 20(1977)623.","journal-title":"Commun. ACM"},{"key":"BF01874396_CR70","volume-title":"Probabilistic algorithms","author":"M.O. Rabin","year":"1979","unstructured":"M.O. Rabin, Probabilistic algorithms, IBM Research Division, San Jose-Yorktown-Zurich, Report RC 6164(1979)."},{"key":"BF01874396_CR71","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1137\/0209024","volume":"9","author":"M.O. Rabin","year":"1980","unstructured":"M.O. Rabin, Probabilistic algorithms in finite fields, SIAM J. Comput. 9(1980)273.","journal-title":"SIAM J. Comput."},{"key":"BF01874396_CR72","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"M.O. Rabin","year":"1980","unstructured":"M.O. Rabin, Probabilistic algorithms for testing primality, J. Number Theory 12(1980)128.","journal-title":"J. Number Theory"},{"key":"BF01874396_CR73","unstructured":"M.O. Rabin, Fingerprinting by random polynomials, Research Report TR-15-81, Aiken Computation Laboratory, Harvard University (1981)."},{"key":"BF01874396_CR74","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/0022-0000(82)90010-1","volume":"25","author":"M.O. Rabin","year":"1982","unstructured":"M.O. Rabin,N-process synchronisation by a 4 logN-valued shared variable. J. Comp. Syst. Sci. 25(1982)66.","journal-title":"J. Comp. Syst. Sci."},{"key":"BF01874396_CR75","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1145\/322290.322306","volume":"29","author":"C. Rackoff","year":"1982","unstructured":"C. Rackoff, Relativized questions involving probabilistic algorithms, J. ACM 29(1982)261.","journal-title":"J. ACM"},{"key":"BF01874396_CR76","doi-asserted-by":"crossref","unstructured":"J.H. Reif, Logics for probabilistic programming, Proc. 12th ACM Symp. Theory Comput. (1980) p. 8.","DOI":"10.1145\/800141.804647"},{"key":"BF01874396_CR77","series-title":"Proc. ICALP","first-page":"442","volume-title":"On the power of probabilistic choice in synchronous parallel computations","author":"J.H. Reif","year":"1982","unstructured":"J.H. Reif, On the power of probabilistic choice in synchronous parallel computations, Proc. ICALP, ed. M. Nielsen and E.M. Schmidt (Springer Verlag, Berlin, 1982) p. 442."},{"key":"BF01874396_CR78","unstructured":"J.H. Reif and P.G. Spirakis, Probabilistic analysis of random extension\u2014rotation algorithms, Res. Rep. TR-28-81 (Aiken Computation Laboratory, Harvard University, 1981)."},{"key":"BF01874396_CR79","doi-asserted-by":"crossref","unstructured":"J.H. Reif and L. Valiant, A logarithmic-time sort for linear size networks, Proc. 15th ACM Symp. Theory Comput. (1983) p. 10.","DOI":"10.1145\/800061.808727"},{"key":"BF01874396_CR80","doi-asserted-by":"crossref","unstructured":"R. Reischuk, A fast probabilistic parallel sorting algorithm, Proc. 22th Symp. Found. Comput. Sci. (1981) p.","DOI":"10.1109\/SFCS.1981.6"},{"key":"BF01874396_CR81","first-page":"864","volume":"13","author":"S. Reiter","year":"1965","unstructured":"S. Reiter and G. Sherman, Discrete optimizing, SIAM J. 13(1965)864.","journal-title":"SIAM J."},{"key":"BF01874396_CR82","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/0020-0190(78)90039-X","volume":"7","author":"F.J. Rohlf","year":"1978","unstructured":"F.J. Rohlf, A probabilistic minimum spanning tree algorithm, Inf. Proc. Lett. 7(1978) 44.","journal-title":"Inf. Proc. Lett."},{"key":"BF01874396_CR83","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1287\/opre.17.3.455","volume":"17","author":"R. Roth","year":"1969","unstructured":"R. Roth, Computer solutions to minimum-cover problems, Oper. Res. 17(1969)455.","journal-title":"Oper. Res."},{"key":"BF01874396_CR84","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1145\/321574.321584","volume":"17","author":"R. Roth","year":"1970","unstructured":"R. Roth, An approach to solving linear discrete optimization problems. J. ACM 17(1970) 303.","journal-title":"J. ACM"},{"key":"BF01874396_CR85","doi-asserted-by":"crossref","unstructured":"V.L. Ruzzo, J. Simon and M. Tompa, Space-bounded hierarchies and probabilistic computations, Proc. 14th ACM Symp. Theory Comput. (1982) p. 215.","DOI":"10.1145\/800070.802194"},{"key":"BF01874396_CR86","doi-asserted-by":"crossref","first-page":"704","DOI":"10.1090\/S0002-9939-1969-0249221-4","volume":"22","author":"E.S. Santos","year":"1969","unstructured":"E.S. Santos, Probabilistic Turing machines and computability, Proc. Amer. Math. Soc. 22 (1969) p.704.","journal-title":"Proc. Amer. Math. Soc."},{"key":"BF01874396_CR87","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1090\/S0002-9947-1971-0281555-3","volume":"4","author":"E.S. Santos","year":"1971","unstructured":"E.S. Santos, Computability by probabilistic Turing machines, Trans. Amer. Math. Soc. 4 (1971)165.","journal-title":"Trans. Amer. Math. Soc."},{"key":"BF01874396_CR88","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF01580681","volume":"10","author":"S.L. Savage","year":"1976","unstructured":"S.L. Savage, Some theoretical implications of local optimization, Math. Progr 10(1976)354.","journal-title":"Math. Progr"},{"key":"BF01874396_CR89","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"J.T. Schwartz, Fast probabilistic algorithms for verification of polynomial identies, J. ACM 27(1980)701.","journal-title":"J. ACM"},{"key":"BF01874396_CR90","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF00289467","volume":"7","author":"R. Sedqewick","year":"1977","unstructured":"R. Sedqewick, The analysis of quicksort programs, Acta Inf. 7(1977)327.","journal-title":"Acta Inf."},{"key":"BF01874396_CR91","first-page":"480","volume":"52","author":"J. Simon","year":"1977","unstructured":"J. Simon, On the difference between the one and the many, Automata Languages and Programming, Springer Lecture Notes in Comp. Sc. 52(1977) p. 480.","journal-title":"On the difference between the one and the many, Automata Languages and Programming, Springer Lecture Notes in Comp. Sc."},{"key":"BF01874396_CR92","doi-asserted-by":"crossref","unstructured":"J. Simon, Space-bounded probabilistic Turing machine complexity classes are closed under complement, Proc. 13th ACM Symp. Theory Comput. (1981) p. 158.","DOI":"10.1145\/800076.802469"},{"key":"BF01874396_CR93","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1145\/362875.362901","volume":"12","author":"R.C. Singleton","year":"1969","unstructured":"R.C. Singleton, Algorithm A 347: an efficient algorithm for sorting with minimal storage, Comm. ACM 12(1969)185.","journal-title":"Comm. ACM"},{"key":"BF01874396_CR94","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","volume":"6","author":"R. Solovay","year":"1977","unstructured":"R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977)84.","journal-title":"SIAM J. Comput."},{"key":"BF01874396_CR95","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1137\/0207009","volume":"7","author":"R. Solovay","year":"1978","unstructured":"R. Solovay and V. Strassen, Erratum: A fast Monte-Carlo test for primality, SIAM J. Comput. 7(1978)118.","journal-title":"SIAM J. Comput."},{"key":"BF01874396_CR96","doi-asserted-by":"crossref","first-page":"455","DOI":"10.1109\/TCT.1969.1083004","volume":"16","author":"K.P. Steiglitz","year":"1969","unstructured":"K.P. Steiglitz, P. Weiner and D.J. Kleitman, The design of minimal cost survivable networks, IEEE Trans. Cir. Theory, CT 16(1969) p. 455.","journal-title":"IEEE Trans. Cir. Theory, CT"},{"key":"BF01874396_CR97","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"L.J. Stockmeyer, The polynomial-time hierarchy, Theor. Comp. Sc. 3(1977)1.","journal-title":"Theor. Comp. Sc."},{"key":"BF01874396_CR98","series-title":"Proc. Math. Found. Comput. Sci.","first-page":"125","volume-title":"On problems solvable by successive trials","author":"B.A. Trakhtenbrot","year":"1975","unstructured":"B.A. Trakhtenbrot, On problems solvable by successive trials, Proc. Math. Found. Comput. Sci., ed. G. Goos and J. Hartmanis (Springer-Verlag, Berlin, 1975) p. 125."},{"key":"BF01874396_CR99","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"L.G. Valiant, The complexity of enumeration and reliability problems, SIAM J. Comput. 8(1979)410.","journal-title":"SIAM J. Comput."},{"key":"BF01874396_CR100","series-title":"Res. Rep.","volume-title":"A probabilistic stopping rule for randomized algorithms","author":"C. Vercellis","year":"1981","unstructured":"C. Vercellis, A probabilistic stopping rule for randomized algorithms, Res. Rep. Nr. 81. 2 (Ist. App. Mat. Inf.), CNR, Milano, 1981)."},{"key":"BF01874396_CR101","series-title":"Res. Rep.","volume-title":"A probabilistic analysis of the set covering problem","author":"C. Vercellis","year":"1982","unstructured":"C. Vercellis, A probabilistic analysis of the set covering problem, Res. Rep. No. 82.9 (Ist. Appl. Mat. Inf.), CNR, Milano, 1982)."},{"key":"BF01874396_CR102","series-title":"Report CMU-CS-78-142","volume-title":"Statistical methods in algorithmic design and analysis","author":"B.W. Weide","year":"1978","unstructured":"B.W. Weide, Statistical methods in algorithmic design and analysis, Ph.D. Thesis (Carnegie-Mellon University, Pittsburgh, PA, Computer Sci. Dept.) Report CMU-CS-78-142 (1978)."},{"key":"BF01874396_CR103","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1016\/0166-218X(83)90023-9","volume":"5","author":"D.J.A. Welsh","year":"1983","unstructured":"D.J.A. Welsh, Randomized algorithms, Discr. Appl. Math. 5(1983)133.","journal-title":"Discr. Appl. Math."},{"key":"BF01874396_CR104","first-page":"127","volume":"5","author":"H.C. Williams","year":"1978","unstructured":"H.C. Williams, Primality testing on a computer, Ars Combinatorica 5(1978)127.","journal-title":"Ars Combinatorica"},{"key":"BF01874396_CR105","unstructured":"Y. Yacobi and S. Even, A hard-core theorem for randomized algorithms, Tech. Rep. Nr. 188 (Computer Sci. Dept., Technion, 1980)."},{"key":"BF01874396_CR106","series-title":"Computer Sci. Dept., Rep. STAN-CS-77-647","volume-title":"A lower bound to palindrome recognition by probabilistic Turing machines","author":"A.C. Yao","year":"1977","unstructured":"A.C. Yao, A lower bound to palindrome recognition by probabilistic Turing machines (Stanford University, Stanford, California, Computer Sci. Dept., Rep. STAN-CS-77-647, 1977)."},{"key":"BF01874396_CR107","doi-asserted-by":"crossref","unstructured":"A.C. Yao, Probabilistic computations: toward a unified measure of complexity, Proc. 18th Symp. Found. Comput Sci. (1977) p. 222.","DOI":"10.1109\/SFCS.1977.24"},{"key":"BF01874396_CR108","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume":"72","author":"R.E. Zippel","year":"1979","unstructured":"R.E. Zippel, Probabilistic algorithms for sparse polynomials, Springer Lecture Notes in Comput. Sci. 72(1979) p. 216.","journal-title":"Springer Lecture Notes in Comput. Sci."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01874396.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01874396\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01874396","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,8]],"date-time":"2020-04-08T03:46:06Z","timestamp":1586317566000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01874396"}},"subtitle":["In alphabetical order"],"short-title":[],"issued":{"date-parts":[[1984,10]]},"references-count":108,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1984,10]]}},"alternative-id":["BF01874396"],"URL":"https:\/\/doi.org\/10.1007\/bf01874396","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"value":"0254-5330","type":"print"},{"value":"1572-9338","type":"electronic"}],"subject":[],"published":{"date-parts":[[1984,10]]}}}