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