Brown CS News

Last update on .

Eli Upfal Publishes A Much-Expanded Second Edition Of

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.