Brown CS News

Click the link that follows for more Brown CS content about Eli Upfal.

Professor Eli Upfal of Brown University's Department of Computer Science (Brown CS) and Michael Mitzenmacher of Harvard University have just released a significantly larger second edition of their widely-used textbook, Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. It's already receiving high praise from experts in the field: Stanford University's Donald E. Knuth says, "This textbook provides a rigorous yet accessible introduction to fundamental concepts that need to be widely known. The new chapters in this second edition, about sample size and power laws, make it especially valuable for today's applications." Richard Karp of University of California, Berkeley, explains that his favorite course that he's taught at Berkeley is one based on Probability and Computing: "Students appreciate the clarity and crispness of the arguments and the relevance of the material to the study of algorithms." 

Readers of the book need only an elementary background in discrete mathematics, and the new material covers such topics as normal distributions, sample complexity, VC dimension, Rademacher complexity, power laws and related distributions, cuckoo hashing, and the Lovasz Local Lemma. A full list of contents includes:

1. Events and probability
2. Discrete random variables and expectations
3. Moments and deviations
4. Chernoff and Hoeffding bounds
5. Balls, bins, and random graphs
6. The probabilistic method
7. Markov chains and random walks
8. Continuous distributions and the Polsson process
9. The normal distribution
10. Entropy, randomness, and information
11. The Monte Carlo method
12. Coupling of Markov chains
13. Martingales
14. Sample complexity, VC dimension, and Rademacher complexity
15. Pairwise independence and universal hash functions
16. Power laws and related distributions
17. Balanced allocations and cuckoo hashing

Eli explains that the book's new subtitle (it changes from "Randomizing Algorithms and Probabilistic Analysis" to "Randomization and Probabilistic Techniques in Algorithms and Data Analysis") is significant. "The new material is mostly related to the theory of machine learning and data analysis," he says, "following their growing importance in CS. We want students to learn the best modern techniques and applications, so we provide many new exercises and examples, including programming-related ones that provide training in solving these kinds of problems."

The image above is © 2017 by Cambridge University Press.

For more information, please click the link that follows to contact Brown CS Communication Outreach Specialist Jesse C. Polhemus.