0 0 15 views

**Unformatted text preview:**

Review3 of Probability and Computing Randomized Algorithms and Probabilitic Analysis Author of Book Michael Mitzenmacher and Eli Upfal Publisher Cambridge University Press 2005 Cost 55 00 hardcover Reviewer Jonathan Katz Dept of CS Univ of MD Randomized algorithms and basic techniques of probabilistic analysis are essential components of the theoretical computer scientist s tool kit indeed their applications have become so widespread that they should be and increasingly are part of every computer scientist s tool kit Randomization has of course proved useful in designing traditional algorithms interestingly here we don t actually know whether randomization truly helps at least in the sense that we don t have a proof that P 6 BPP but in practice randomized algorithms are often more efficient and or simpler than their deterministic counterparts Randomization is also essential in a provable sense for cryptography and for certain results in distributed computing Finally a good understanding of random processes 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 inputs are not chosen deterministically Because of the widespread interest in the subject a textbook covering randomization in computer science must be many things to many different people it should serve as an introduction to the area for an undergraduate or graduate student interested in randomized algorithms a survey of applications and techniques for the general computer scientist and also a solid reference for the advanced researcher I am pleased to say that Probability and Computing succeeds on all these fronts I found the book a joy to read the writing is clear and concise the proofs are well structured and the writing style invites the reader to explore the material The book is also organized very well and the selection of topics is excellent I have already used the book multiple times as a reference and have found it incredibly useful each time The chapters of the book can roughly be classified in three sections essentially as suggested by the authors in the preface introductory material and review basic material of the sort that might constitute an undergraduate course on the subject and more advanced material for a graduate course or independent study The introductory material in which I would include Chapters 1 and 2 begins with a review of basic probability theory along with some standard applications to motivate the study of the subject Chapter 2 includes a discussion of random variables and their expectation and also introduces the Bernoulli binomial and geometric distributions It is fair to say that the treatment here is meant as a review for the student who has had some prior exposure to probability 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 material such as Markov s inequality Chebyshev s inequality and Chernoff bounds are included in the book s coverage of this material I especially appreciated the applications that are stressed throughout and are covered at a good level of detail Chapter 5 covers the balls into bins probabilistic model and the Poisson distribution again giving a wealth of realistic examples to continually motivate 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 randomized 3 c 2007 Jonathan Katz 7 algorithms I think these chapters with some material cut so as to go at a slower pace would also work well as a tough undergraduate course Indeed the authors have used parts of this book in undergraduate courses taught at Harvard and Brown In particular I think the writing is friendly enough to suit the dedicated undergraduate and the focus on interesting applications of the material would catch the interest of an undergraduate even if they were not solely interested in theory The remaining seven chapters of the book could be used as the core of a second semester graduate course for self study or for reference I quite liked the selection of topics here these include chapters covering continuous distributions the basics of entropy and information theory Monte Carlo methods martingales and the Azuma Hoeffding inequality and pairwise independence universal hash functions and more My only quibble here is that I would have liked to see the chapter on pairwise independence earlier this material is both more central and less difficult than the other material included in these advanced chapters and so I don t see why it comes so late 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 algorithms in terms of its breadth depth and accessibility It will serve handily as a reference or as a guide to self study and belongs on the bookshelf of every graduate student and computer scientist interested in the role of randomization in computing Review4 of Probability and Computing Randomized Algorithms and Probabilitic Analysis Authors of Book Michael Mitzenmacher and Eli Upfal Publisher Cambridge University Press 2005 Cost 55 00 hardcover Reviewer Yannis C Stamatiou 1 Introduction The 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 step following in a unique way from the previous step is very old and touches the borders between philosophy and science Isaac Newton s feat to describe neatly and orderly the evolution of the movement 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 Poincare s work about the inability to solve the equations precisely even if the world behaves deterministically and then more fundamentally by quantum physics which completely defied the deterministic point of view The authors discuss the points above right from the very beginning of the book and conclude that randomness seems to be here to stay while in addition it can be put into very good use in algorithmics and complexity theory This book thus is about how randomness can be harnesses