# Monthly Archives: February 2015

## HW4 addendum

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.

## Lecture 18: Chernoff Bounds

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

## Lecture 17: Convex Bodies and Ellipsoid

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

## Lecture 16: Gradient Descent

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

## Homework #4

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.

## Lecture 15(b): Illustrative Examples

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

## Lecture 15: Max-Flows using Electrical Flows

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