Monthly Archives: February 2015

For problem #1, you may assume that you are in the bipartite graph case. (You can get bonus points for doing the non-bipartite case.) I’ve updated the PDF accordingly.

The comment at the end about the moment bounds being at least as good as the Chernoff-type bounds is actually a really simple idea. Say we’re working with non-negative random variables. Recall the Chernoff uses something like We could have … Continue reading →

Yesterday we talked about the center of gravity; since some of you had not seen that before, the formula can seem somewhat mysterious. But it’s the natural extension of the discrete case, which you may have seen before, e.g., even … Continue reading →

Euiwoong asked about what happens with constrained linear function optimization (which are -smooth), since this could solve LPs. So a minor issue is that the proofs require , since they first set , which will be disastrous in this case. … Continue reading →

On the webpage, and here. Due on Feb 27th. I will be away that day, so you’ll have to submit it to Euiwoong directly — we’ll figure out a plan soon. 4 problems. Questions, comments, clarifications below.

Here’s an example from the Christiano et al. paper that shows that the width of the basic electrical flow oracle could be as large as . The effective resistance of the black edges is , so half the current flows … Continue reading →

In class we saw an algorithm to find -approximate max-flows in time for undirected graphs with unit capacities. In class, we said: if there exists a flow of value that respects all the capacities, we find flows that achieve value … Continue reading →

A clarification about today’s lecture: The Oracle. My explanation for why the oracle was an easy problem was not very clear. Let me try again. Let us define Notice that this has non-negativity constraints, and one equality constraint. Very simple … Continue reading →

A couple things: Jason pointed out that one can use Lovasz’ basic idea with binary search to actually reduce the number of calls from to , and hence get an algorithm using very basic techniques.His approach is this: suppose we … Continue reading →

The lower bound for the matching polytope is actually the following: if you can write linear inequalities to define the perfect matching polytope on the complete graph (i.e., so that the resulting polytope is equal to the convex hull of … Continue reading →