Category Archives: Uncategorized

Nicholas asked how, in the SoS example where we wanted to write the polynomial as a sum of square polynomials, we could quickly restrict ourselves to . Here’s one way. Of course, in general we have to consider the vector … Continue reading →

So two things that we wanted to check during lecture today, and some notes: If is sub-Gaussian with parameter , and they are independent, then is indeed sub-Gaussian with parameter , as claimed. Basically, just use the MGF definition to … Continue reading →

Some of you asked for intuition about matroids: they seem so abstract, how to think about them? Whenever I have to prove a fact about matroids, I think about how I’d prove the fact for graphic matroids. And often (though … Continue reading →

Pranav and Sidhanth asked me for the motivation behind that problem: why did we just not find a perfect matching in the graph (say by the blossom algorithm), put weight 0 on the matching edges, and 1s elsewhere? The reason … Continue reading →

Hi all: since we covered most of the short-step method today, it may be easiest if you looked over the proof yourself. We can discuss it in office hours on Tuesday, if you’d like. I’d like to start off talking … Continue reading →

We will talk a bit more about the Ellipsoid algorithm (and separation vs optimization) on Friday, maybe start talking about the Newton method, and then move on to more details on interior point techniques on Monday. A couple things about … Continue reading →

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 →

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 →

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 →

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 →