Monthly Archives: February 2017

Lec #12: Notes on solving LPs

Notes for today’s lecture: Tightness of the Hedge guarantee. Consider the basic Hedge analysis, which says that for any , we have regret at most . Now if we were to set by balancing those terms, the regret bound would … Continue reading

Posted in Uncategorized | Leave a comment

Lec #9:Notes

A few loose ends from yesterday’s lecture: The formula for computing inverses of a submatrix from the inverse of the whole thing is given by this: (from this survey by Pawel Parys). A good explanation of the Mucha and Sankowski … Continue reading

Posted in Uncategorized | Leave a comment

Lec #7: Notes

Today we saw several definitions and facts about polytopes, including proofs of the integrality of the perfect matching polytope for bipartite graphs. Some comments. We saw the definition of the perfect matching polytope for non-bipartite graphs (with exponentially many constraints), … Continue reading

Posted in Uncategorized | Leave a comment

Lec #4: Notes

Some more notes about today’s lecture: We know that , and in a forthcoming homework we will remove this log factor. The reduction in the other direction is not that mysterious: given two matrices , , can you write down … Continue reading

Posted in Uncategorized | Leave a comment

Fredman’s Trick

OK, sorry, I was being silly. We wanted to compute MSP of two matrices and . I.e, we wanted , say. (Notice that I’ve transposed .) In words, this is If is the minimizer of this expression then which is … Continue reading

Posted in Uncategorized | Leave a comment