Talk:CS 6963 Summaries

From ResearchWiki

28 Aug

Nathan

Is it possible for objects in your chosen probability space S to have a zero probability, or do all objects in S contain the properties desired for your application?

(Piyush): For the former question, the answer, in principle, is yes. But usually the probability space S is constructed appropriately by posing certain restrictions on it so that we end up getting a non-zero probability of existence. These restrictions, however, would usually be reasonable ones. For example, in the monochromatic subgraph problem, we assume that , which would indeed be a reasonable assumption for many problem instances. On the other hand, for the latter question, it would be highly unlikely (and probably uninteresting) to have a case when all objects in S have the desirable properties.

Scott

In section 6.4.2, when it says "", what does the notion "G_n,p" mean?

(Piyush): G_n,p is a random graph with n nodes that probability p of having an edge between any two nodes.

Amit

I am not able to convince myself the max cut size be at least m/2. I buy the later argument that we need at most m/2 +1 samples to find a cut with at least m/2 edges.

(Piyush) Note that the probability that an edge e_i connects a vertex in A to a vertex in B is 1/2. To see this, consider both vertices (say v₁ and v₂) associated with e_i. Since we are assigning v₁ and v₂ to sets A or B randomly and independently, the probability that they go to different sets (i.e. one to A and the other to B) is 1/2. If it is still unclear, think of this: you can assign the first vertex to any of the sets (say A) with probability 1. But then you must assign the second vertex to the other set (B), with probability 1/2. Since these two events are independent, we get an overall probability of 1/2. Invoking the linearity of expectation argument, we get the m/2 lower bound on the max cut size.

Rob

In the analysis of the Las Vegas algorithm for the coloring problem (or, in general, any other Las Vegas algorithm), is it possible to prove the algorithm always completes in polynomial time, or can we simply prove that it completes in polynomial time with high probability? (For example, we can imagine that there is only one value for the random variable(s) that leads the algorithm to find a correct solution, but a truly random distribution is not guaranteed to return that value within a particular (finite) number of trials - it's just probable that it will.)

(Piyush) The Las Vegas algorithm assumes conditions (i.e. sample size and the verification algorithm both should be polynomial in the problem size) that, in polynomial time, guarantee a correct solution or the non-existence of such a solution. If the assumed conditions are not met, you cannot have a Las Vegas algorithm for the problem. In your case, the sample size clearly is not polynomial in the problem size. So, by definition, it cannot be called a Las Vegas algorithm.