### Blogroll

### Pages

### Recent Posts

Advertisements

Randomized Algorithms, Carnegie Mellon: Spring 2011

April 17, 2011

Posted by on HW#6 is out, it’s a short one. Due next Wednesday April 27th.

Advertisements

%d bloggers like this:

Problem 2.B does not specify the expansion of the constant-degree expander graph. Are we supposed to assume that \epsilon + \sqrt{\delta} < 1 or are we supposed to prove something like this? (where \epsilon = |\lambda_2| is the second largest eigenvalue of the transition matrix M of our graph)

Ideally, you should be able to show that no matter what expander you construct, it doesn’t matter: the only thing that changes is the constant implicit in the in the failure probability bound of .

But failing that, go ahead and assume that .

More clarification: let’s define .

Now in part b, ideally you should be able to show that as long as you start off with an expander with bounded away from 1, you still get the exponential decay in the error probability. Note that for this setting of , it may not be the case that

, so you cannot just directly apply part (a), and you have to do a little more work.

However, if that doesn't seem to be working out, go ahead and assume that the expander you choose in (b) has .

And yeah, go ahead and assume the expander is a regular graph.

For exercise 1, can we flip positives and negatives? That is, if the rectangle can separate all the negatives and positives by having all the negatives inside the rectangle, does that count as a correct classification?

No – everything inside the rectangle is positive and everything outside is negative.