# Category Archives: Uncategorized

## Lec #24: SDPs I

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

## Lec #19: JL etc.

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

## Matroids

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

## A comment about HW3 #5

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

## Lec #17: Ellipsoid and Interior-Point

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

## Lec #16: Ellipsoid and Center-of-Gravity

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

## 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