Monthly Archives: March 2012

Lecture 23: Random partitions of metric spaces (continued)

We continue our theorem from last time on random partitions of metric spaces 1. Review of Previous Lecture Define the partial Harmonic sum . Let be the ball of radius around . Theorem 1 Let be a metric with . … Continue reading

Posted in Uncategorized | Leave a comment

Lecture 22: Random partitions of metric spaces

For many problems in computer science, there is a natural notion of “distance”. For example, perhaps the input data consists of real vectors for which it makes sense to measure their distance via the usual Euclidean distance. But in many … Continue reading

Posted in Uncategorized | Leave a comment

Lecture 21: Property Testing

1. Overview of Property Testing Property testing is a research area in theoretical computer science that has seen a lot of activity over the past 15 years or so. A one-sentence description of this area’s goal is: design algorithms that, … Continue reading

Posted in Uncategorized | Leave a comment

Lecture 20: Expanders, Superconcentrators

Today we will make a brief excursion into the fascinating world of expander graphs. It is hard to overstate the importance of these objects to theoretical computer science. They play an important role in some astonishing algorithms, the PCP theorem, … Continue reading

Posted in Uncategorized | 1 Comment

Lecture 19: The Lovasz Local Lemma

Today’s lecture introduces a completely new topic: the Lovász Local Lemma (LLL). This is an important method for analyzing events that are not independent, but have some restricted sort of dependencies. It is not as widely applicable as many of … Continue reading

Posted in Uncategorized | Leave a comment

Lecture 18: Perfect Hashing

In the last lecture we defined the notion of pairwise independence, and saw some ways to use this concept in reducing the randomness of a randomized algorithm. Today we will apply these ideas to designing hash functions and “perfect” hash … Continue reading

Posted in Uncategorized | Leave a comment

Lecture 17: Chebyshev’s Inequality, Pairwise Independence

So far we have seen two concentration bounds for scalar random variables: Markov and Chernoff. For our sort of applications, these are by far the most useful. In most introductory probability courses, you are likely to see another inequality, which … Continue reading

Posted in Uncategorized | 1 Comment