
Recent Posts
Archives
Categories
Meta
Advertisements
1. Compressed Sensing Let be some unknown vector. We can learn information about through the following “measurement” operation: we can choose a vector and we are told the value of . We would like to minimize the number of measurements … Continue reading
In this lecture we will see two applications of the JohnsonLindenstrauss lemma. 1. Streaming Algorithms In 1996, Alon, Matias and Szegedy introduced the streaming model of computation. Given that they all were at AT&T Labs at the time, their work … Continue reading
Dimensionality reduction is the process of mapping a high dimensional dataset to a lower dimensional space, while preserving much of the important structure. In statistics and machine learning, this often refers to the process of finding a few directions in … Continue reading
In this lecture we continue to discuss applications of randomized algorithms in computer networking. 1. Analysis of SkipNet Routing Last time we introduced the SkipNet peertopeer system and we discussed its routing protocol. Recall that every node has a string … Continue reading
In today’s lecture we will see two applications of negative binomially distributed random variables. 1. Example: Quicksort Quicksort is one of the most famous algorithms for sorting an array of comparable elements. (We assume for simplicity that the array has … Continue reading
1. Example: Balls and Bins Last time we proved the Chernoff bound, the most useful analysis tool we will encounter in this course. Today we illustrate the power of the Chernoff bound by using it to analyze a fundamental ballsandbins … Continue reading
In the analysis of randomized algorithms, we frequently use various inequalities to simplify expressions or make them easier to work with. These inequalities are usually obvious by plotting them, and proving them just uses basic calculus. 1. Facts from Convex … Continue reading