Rajeev Motwani
- ALELIUNAS, R. 1982. Randomized parallel communication. In ACM-SIGOPS Symposium on Principles of Distributed Systems, 60 -72. Google Scholar
- ALON, N. AND SPENCER, J. 1992. The Probabilistic Method. Wiley, New York.Google Scholar
- BERLEKAMP, E.R. 1970. Factoring polynomials over large finite fields. Math. Comput. 24, 713-735.Google Scholar
- CARTER, J. L. AND WEGMAN, M. N. 1979. Universal classes of hash functions. J. Cornput. Syst. Sci. 18, 2, 143-154.Google Scholar
- DE LEEUW, K., MOORE, E. F., SHANNON, C. E., AND SHAPIRO, N. 1955. Computability by probabilistic machines. In Automata Studies, C. E. Shannon and J. McCarthy, Eds., Princeton University Press, Princeton, NJ, 183-212.Google Scholar
- FLOYD, R. W. AND RIVEST, R.L. 1975. Expected time bounds for selection. Commun. ACM 18, 165-172. Google Scholar
- FREIVALDS, R. 1977. Probabilistic machines can use less running time. In Information Processing 77, Proceedings of IFIP Congress 77, B. Gilchrist, Ed., (Aug.), North-Holland, Amsterdam, 839-842.Google Scholar
- GILL, J. 1977. Computational complexity of probabilistic Turing machines. SIAM J. Cornput. 6, 4 (Dec.), 675-695.Google Scholar
- HOARE, C. A.R. 1962. Quicksort. Comput. J. 5, 10 -15.Google Scholar
- JERRUM, M. R. AND SINCLAIR, A. 1989. Approximating the permanent. SIAM J. Cornput. 18, 6 (Dec.), 1149-1178. Google Scholar
- JOHNSON, D. S. 1984a. The NP-completeness column: An ongoing guide. J. Algorithms 5, 284 -299. Google Scholar
- JOHNSON, D. S. 1984b. The NP-completeness column: An ongoing guide. J. Algorithms 5, 433-447. Google Scholar
- KARP, R.M. 1991. An introduction to randomized algorithms. Discrete Appl. Math. 34, 165- 201. Google Scholar
- KARP, a. M. AND RABIN, M. O. 1987. Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31 (March), 249-260. Google Scholar
- MAFFIOLI, F., SPERANZA, M. G., AND VERCELLIS, C. 1985. Randomized algorithms. In Combinatorial Optimization: Annotated Bibliographies, M. O'hEigertaigh, J.K. Lenstra, and A.H.G. Rinooy Kan, Eds., Wiley, New York, 89 -105.Google Scholar
- MOTWANI, R. AND RAGHAVAN, P. 1995. Randomized Algorithms. Cambridge University Press, New York. World-Wide Web information at http://www.cup.org/Reviews&blurbs/ RanAlg/RanAlg.html. Google Scholar
- MULMULEY, K. 1993. Computational Geometry: An Introduction Through Randomized Algorithms. Prentice Hall, New York.Google Scholar
- MULMULEY, K., VAZIRANI, U. Y., AND VAZIRANI, Y. V. 1987. Matching is as easy as matrix inversion. Combinatorica 7, 105-113. Google Scholar
- RABIN, M. O. 1982. The choice coordination problem. Acta Inf. 17, 121-134.Google Scholar
- RABIN, M. O. 1980. Probabilistic algorithm for testing primality. J. Number Theory 12, 128- 138.Google Scholar
- RABIN, M.O. 1976. Probabilistic algorithms. In Algorithms and Complexity, Recent Results and New Directions, J.F. Traub, Ed., Academic Press, New York, 21-39.Google Scholar
- RABIN, M.O. 1963. Probabilistic automata. Inf. Control 6, 230-245.Google Scholar
- SINCLAIR, A. 1992. Algorithms for Random Generation and Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkhauser, Boston. Google Scholar
- SNIR, M. 1985. Lower bounds on probabilistic linear decision trees. Theor. Comput. Sci. 38, 69-82.Google Scholar
- SOLOVAY, R. AND STRASSEN, V. 1977. A fast Monte-Carlo test for primality. SIAM J. Cornput. 6, I (March), 84-85. See also SIAM J. Comput. 7, I (Feb.), 1978, 118.Google Scholar
- UPFAL, E. 1984. Efficient schemes for parallel communication. J. ACM 31, 507-517. Google Scholar
- VALIANT, L.G. 1982. A scheme for fast parallel communication. SIAM J. Comput. 11, 350- 361.Google Scholar
- WELSH, D. J.A. 1983. Randomised algorithms. Discrete Appl. Math. 5, 133-145.Google Scholar
- YAO, A. C-C. 1977. Probabilistic computations: Towards a unified measure of complexity. In Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 222-227.Google Scholar
Index Terms
- Randomized algorithms
Recommendations
Randomized algorithms
This tutorial will illustrate the power of randomization in algorithms. The history of algorithms begins with deterministic algorithms. Deterministic algorithms are more natural, are usually easier to analyze, and are usually easier to understand by ...
Constant-Time Randomized Parallel String Matching
Given a pattern string of length m for the string-matching problem, we design an algorithm that computes deterministic samples of a sufficiently long substring of the pattern in constant time. This problem used to be the bottleneck in the pattern ...
Super-linear time-space tradeoff lower bounds for randomized computation
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer ScienceWe prove the first time-space lower bound tradeoffs for randomized computation of decision problems. The bounds hold even in the case that the computation is allowed to have arbitrary probability of error on a small fraction of inputs. Our techniques ...
Comments