Monthly Archives: March 2012

Lecture 16: Derandomization: Method of Conditional Expectations, Method of Pessimistic Estimators

In this lecture we discuss the topic of derandomization — converting a randomized algorithm into a deterministic one. 1. Method of Conditional Expectations One of the simplest methods for derandomizing an algorithm is the “method of conditional expectations”. In some … Continue reading

Posted in Uncategorized | 1 Comment