
Recent Posts
Archives
Categories
Meta
Category Archives: Uncategorized
Lecture 25: Online Steiner Tree
The algorithm for probabilistically embedding metric spaces into trees has numerous theoretical applications. It is a key tool in the design of many approximation algorithms and online algorithms. Today we will illustrate the usefulness of these trees in designing an … Continue reading
Posted in Uncategorized
Leave a comment
Lecture 24: Probabilistic approximation of metrics by trees
1. Probabilistic Approximation of Metrics For many optimization problems, the input data involves some notion of distance, which we formalize as a metric. But unfortunately many optimization problems can be quite difficult to solve in an arbitrary metric. In this … Continue reading
Posted in Uncategorized
Leave a comment
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 onesentence 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