Review3ofProbability and Computing: Randomized Algorithms and Probabilitic AnalysisAuthor of Book: Michael Mitzenmacher and Eli UpfalPublisher: Cambridge University Press, 2005Cost: $55.00, hardcoverReviewer: Jonathan Katz, Dept of CS, Univ of MD.Randomized algorithms and basic techniques of probabilistic analysis are essential componentsof the theoretical computer scientist’s tool-kit; indeed, their applications have become so widespreadthat they should be (and, increasingly, are) part of every computer scientist’s tool-kit. Random-ization has of course proved useful in designing traditional algorithms; interestingly, here we don’tactually know whether randomization truly “helps” (at least in the sense that we don’t have a proofthat P 6= BPP), but in practice randomized algorithms are often more efficient and/or simpler thantheir deterministic counterparts. Randomization is also essential (in a provable sense) for cryptog-raphy and for certain results in distributed computing. Finally, a good understanding of randomprocesses is also needed any time one is trying to analyze a system that evolves probabilistically,or trying to bound the performance of an algorithm (even a deterministic one!) when the inputsare not chosen deterministically.Because of the widespread interest in the subject, a textbook covering randomization in com-puter science must be many things to many different people: it should serve as an introduction tothe area for an undergraduate or graduate student interested in randomized algorithms; a surveyof applications and techniques for the general computer scientist; and also a solid reference forthe advanced researcher. I am pleased to say that Probability and Computing . . . succeeds onall these fronts. I found the book a joy to read: the writing is clear and concise, the proofs arewell-structured, and the writing style invites the reader to explore the material. The book is alsoorganized very well, and the selection of topics is excellent. I have already used the book multipletimes as a reference, and have found it incredibly useful each time.The chapters of the book can roughly be classified in three sec tions (essentially as suggested bythe authors in the preface): introductory material and review; basic material of the sort that mightconstitute an undergraduate course on the subject; and more advanced material for a graduatecourse or independent study. The introductory material, in which I would include Chapters 1and 2, begins with a review of basic probability theory along with some standard applications tomotivate the study of the subject. Chapter 2 includes a discussion of random variables and theirexpectation, and also introduces the Bernoulli, binomial, and geometric distributions. It is fair tosay that the treatment here is meant as a review for the student who has had some prior exposure toprobability in a discrete mathematics course, and is not meant to teach this material from scratch.The basic material, contained in Chapters 3–7, is actually quite comprehensive. Standard mate-rial such as Markov’s inequality, Chebyshev’s inequality, and Chernoff bounds are included; in thebook’s coverage of this material, I especially appreciated the applications that are stressed through-out and are covered at a good level of detail. Chapter 5 covers the “balls-into-bins” probabilisticmodel and the Poisson distribution, again giving a wealth of realistic examples to continually moti-vate the material. Chapter 6 details the probabilistic method as well as the Lovasz Local Lemma,and Chapter 7 deals with Markov chains and random walks.Chapters 1–7 could form the basis for a solid introductory graduate course on randomized3c2007 Jonathan Katz7algorithms; I think these chapters (with some material cut so as to go at a slower pace) wouldalso work well as a (tough) undergraduate course. (Indeed, the authors have used parts of thisbook in undergraduate courses taught at Harvard and Brown.) In particular, I think the writingis “friendly” enough to suit the dedicated undergraduate, and the focus on interesting applicationsof the mate rial would catch the interest of an undergraduate even if they were not solely interestedin theory.The remaining seven chapters of the book could be use d as the core of a second semestergraduate course, for self-study, or for reference. I quite liked the selection of topics here; theseinclude chapters covering continuous distributions; the basics of entropy and information theory;Monte Carlo methods; martingales and the Azuma-Hoeffding inequality; and pairwise indepen-dence/universal hash functions (and more). My only quibble here is that I would have liked to seethe chapter on pairwise independence earlier; this material is both more central and less difficultthan the other material included in these “advanced” chapters, and so I don’t see why it comes solate in the book. This, however, is a rather minor point.To the best of my knowledge, this book is the best available treatment of randomized algorithmsin terms of its breadth, depth, and accessibility. It will serve handily as a reference or as a guide toself-study, and b e longs on the bookshelf of every graduate student and computer scientist interestedin the role of randomization in computing.Review4ofProbability and Computing: Randomized Algorithms and Probabilitic AnalysisAuthors of Book: Michael Mitzenmacher and Eli UpfalPublisher: Cambridge University Press, 2005Cost: $55.00, hardcoverReviewer: Yannis C. Stamatiou1 IntroductionThe question of whether the evolution of our world obeys a still undiscovered complex set of rules,or to put it in modern terminology, behaves as a deterministic computer algorithm with each stepfollowing in a unique way from the previous step, is very old and touches the borders betweenphilosophy and science. Isaac Ne wton’s feat, to describe neatly and orderly the evolution of themovement of heavenly bodies, seemed to answer this question in the affirmative. Later, however,this venerable and reassuring deterministic point of view was shaken first, “mildly”, by Poincar´e’swork about the inability to solve the equations precisely, even if the world behaves deterministicallyand then, more fundamentally, by quantum physics which completely defied the deterministic pointof view.The authors discuss the points above right from the very beginning of the book and concludethat randomness seems to b e here to stay while,