Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms (Texts in Theoretical Computer Science)

Design and Analysis of Randomized Algorithms: Introduction to Design Paradigms (Texts in Theoretical Computer Science)

Juraj Hromkovič

Language: English

Pages: 280


Format: PDF / Kindle (mobi) / ePub

Randomness is a powerful phenomenon that can be harnessed to solve various problems in all areas of computer science. Randomized algorithms are often more efficient, simpler and, surprisingly, also more reliable than their deterministic counterparts. Computing tasks exist that require billions of years of computer work when solved using the fastest known deterministic algorithms, but they can be solved using randomized algorithms in a few minutes with negligible error probabilities.

Introducing the fascinating world of randomness, this book systematically teaches the main algorithm design paradigms – foiling an adversary, abundance of witnesses, fingerprinting, amplification, and random sampling, etc. – while also providing a deep insight into the nature of success in randomization. Taking sufficient time to present motivations and to develop the reader's intuition, while being rigorous throughout, this text is a very effective and efficient introduction to this exciting field.



















probability space. Let B ⊆ S, Prob(B) ̸= 0, and let ProbB (A) = Prob(A|B) for all A ⊆ B be a function from P(B) to [0, 1]. Prove that (B, ProbB ) is a probability space. Example 2.2.10. Consider the experiment of flipping three coins. To model it we used the probability space (S3 , Prob), where S3 = {(x, y, z) | x, y, z ∈ {head, tail}} and Prob is the uniform probability distribution on S3 . Let A be the event that the outcome involves at least two heads and let B the event that the result of the

question of whether or not true randomness exists, and it is very improbable that science will be able to answer this question in the near future. The reason for this pessimism is that the question about the existence of randomness lies in the very fundamentals of science, i.e., on the level of axioms, and not on the level of results. And, on the level of axioms (basic assumptions), even the exact sciences like mathematics and physics do not have any generally valid assertion, but only

extended Riemann’s Hypothesis holds, then Zp must contain a quadratic nonresidue among its O (log2 p)2 smallest elements, i.e., a quadratic nonresidue can be found deterministically by simply checking all these smallest elements of Zp . 37 This is a direct consequence of the Euler’s criterion (Theorem 5.4.14). This is a consequence of claim (B) (Theorem 5.4.15). 39 if it halts at all 40 Recall the discussion about the random distribution of witnesses in the set of witness candidates. 38 5.5

for primality testing. Since the input length of n is the length ⌈log2 (n + 1)⌉ of its binary representation, we aim to design an algorithm running in time √ Observe that the input size of a positive integer n is ⌈log2 (n + 1)⌉, and so n is exponential in input size. 3 Remember that the method of fingerprinting can be viewed as a special case of the method of abundance of witnesses and so when applying fingerprinting one may speak about witnesses. 2 6.2 Searching for Witnesses for Primality

not only to build the methodology and the machinery for the design of efficient and simple randomized algorithms, but also to capture the nature of the fascinating computational power of randomization in many applications. The paradigms introduced here determine the structure of this book because each of the following chapters (apart from the Appendix) is devoted to the study of one of these paradigms. Chapter 3 provides a deeper insight into the application of the method of fooling an adversary,

Download sample