CMU Randomized Algorithms

Randomized Algorithms, Carnegie Mellon: Spring 2011

HW #6 Open Thread

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


5 responses to “HW #6 Open Thread

  1. Jeremiah April 19, 2011 at 2:21 am

    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)

    • cmurandomized April 19, 2011 at 8:19 am

      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 \Omega in the failure probability bound of 2^{- \Omega(k)}.

      But failing that, go ahead and assume that \epsilon + \sqrt{\delta} < 1.

  2. cmurandomized April 19, 2011 at 2:59 pm

    More clarification: let’s define \epsilon(G) := \max(|\lambda_2|, |\lambda_n|).

    Now in part b, ideally you should be able to show that as long as you start off with an expander with \epsilon(G) bounded away from 1, you still get the exponential decay in the error probability. Note that for this setting of \epsilon(G), it may not be the case that
    (\epsilon(G) + \sqrt{1/2}) < 1, 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 \epsilon(G) < 1 - \sqrt{1/2}.

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

  3. Franklin Ta April 26, 2011 at 3:57 am

    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?

    • Avrim Blum April 26, 2011 at 8:11 am

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

%d bloggers like this: