# Monthly Archives: March 2015

## Homework 6

Hi all: the final HW has been posted. It’s a little longer with 6 questions (the first three are questions you must solve individually, the last three allow collaboration). The due date is April 17th, but see if you can … Continue reading

## Lecture 26: Online Algorithms

Aram asked how the random algorithm does for paging: at each time just pick a random page to evict from the cache. Jason sent in an example where the optimum is 1, but the expected cost for RANDOM is k. … Continue reading

## Lecture #22: Random Sampling for Fast SVDs

Some clarifications from Monday’s lecture (and HW #5): Firstly, Akshay had a question about the Matrix Chernoff bound I mentioned in Lecture today — it seemed to have a weird scaling. The bound I stated said that for , The … Continue reading

## Homework 5

Hi all: Homework 5 has been posted on the webpage. It’s based on Chernoff bounds, some streaming, and a proof of a matrix Chernoff bound, and is due on March 20th. (In 2 weeks or so.) Questions and comments below! … Continue reading

## Lecture 21: SVDs (continued)

Some scribe notes for the lecture are up on the web page. They incorporate two bug fixes, and the proof that the least-squares solution to is indeed , which we did not do in lecture. The bug fixes, so you … Continue reading

## Lecture 21: SVDs

A few things about today’s lecture: This one is kinda important, I meant to discuss it but forgot. We defined as the best-fit one-dimensional subspace, then subject to having fixed . This greedy approach is nice, but one worry is … Continue reading

## Results of the Votes

Hi all: the results of the votes are (in decreasing number of votes): 11 Semidefinite Programming 10 Compressive Sensing 8 Smoothed Analysis 8 Extended Formulations So I’ll go with three of the top four options; probably the first three (the … Continue reading