Talk:CS 6963 Summaries

From ResearchWiki

Revision as of 16:26, 2 September 2008

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.

Tilottama

I have a general question -While choosing to apply either the Counting Argument or the Expectation Argument, is there any intuition as to which method is more suited to a particular problem?

(Piyush) In general, it depends on the problem. Note that the object in consideration is a random variable. If it is possible to express the desired properties as some expected value depending on this random variable, the expectation argument might be preferred. Such were the cases, for example, with the max-cut and maxsat problems.

Parasaran

Given a NP-Hard problem, what tells an algorithm analyst to choose the Randomization (Probabilistic method) or Derandomization (Deterministic Method)?

(Piyush) It depends on the problem structure. If the correctness or feasibility of a randomized algorithm is not satisfactory, one may try derandomization. But whether you can derandomize an randomized algorithm may or may not be possible, again depending on the problem.

In the 'Sample and Modify' Example-1, how do we choose the average degree of the vertex (d) to be 2m/n ?

(Piyush) Each edge is shared between two vertices. Thus the sum of degrees would be 2m. Since there are n vertices, we get an average 2m/n.

Avishek

As we have seen, existential proofs using probabilistic methods can be converted into efficient randomized or deterministic construction algorithms. Although I am not sure, I guess there might be situations/cases where this conversion is not possible.

(Piyush) Yes, there can be situations where a randomized algorithm may not be able to give a satisfactory solution (in term of correctness or feasibility) or a derandomized construction is not possible.

If this is true, then can we in some manner infer from the probabilistic method whether it would be able to give rise to some (randomized or deterministic) construction algorithm or nothing at all ?

(Piyush) If you construct a Monte Carlo algorithm, the success will depend on the probability of getting the correct sample. In you construct a Las Vegas algorithm, it would depend on being able to efficiently sample a candidate solution, sample size, and the time to check whether the solution is correct or not (these values should be polynomial in problem size in order to give a satisfactory solution). Note, however, that some probabilistic methods (such as sample and modify), give us a randomized algorithm as a byproduct of the existence proof itself.

Hal

I don't follow the "sample and modify" algorithm for independent sets. In particular, I don't see why it holds that the vertices obtained by the algorithm form an independent set.

(Piyush) In both the steps, by construction (or "destruction"), we are removing one of the two vertices that are connected by an edge. So at the end, we will never have a vertex pair that was connected originally. And since we end up removing all the edges at the end of step-2, the set of vertices we are left with forms an independent set.

Arvind

I don't understand the step 2 of the "sample and modify" algorithm for independent set.

(Piyush) By deleting an edge (and one of the associated vertices), step-2 just removes one vertex from each pair of vertices that are connected (and hence could never be in an independent set together). This (combined with step-1) leaves us only with a set of vertices that were not connected in the beginning.

Sep 2

Nathan

The first handout shows that the LLL generally produces very low probabilities of existence (but still positive) for your desired object. Are there any tricks to improve this in order to facilitate the creation of efficient algorithms?

(Suresh) there's a considerable amount of discussion on this issue: the most recent paper on the k-SAT problem discusses this in the related work. A celebrated paper by Molloy and Reed from STOC 1998 explored conditions under which the Lovasz local lemma can be converted into an effective algorithm, and citations to this paper reveal much more. Maybe this would also have been a nice project topic !

Scott

Given some problem, I don't see it as always trivial to construct the necessary dependency graph. Since dependency can be hard to detect from sampling, are there ways to relax condition 2 of Theorem 6.11?

(Piyush) We don't have to "construct" the dependency graph. All we need to come up with is an upper bound on the degree of dependency graph which I think should always be possible to obtain from the problem structure. That said, I think it's probably also crucial how tight the upper bound is.

(Amit) I think its not bad to have the upper bound loose (0.1 < 1 is good may not be interesting). The bound bounds the probability of dependence and a bad event at same time.

Parasaran

I don't quite understand how we are arriving at the constant queue size at each edge (Pg 4. in Handout 1). And how does delaying each packet that needs to be routed help?

(Piyush) The handout only provides a portion of the result. In particular, it shows that using LLL, we can prove that every edge has a log(c) congestion in a "frame" (the structure constructed after introducing the random delays). This fact is used later for the rest of the proof which is actually part of Leighton et al. paper (ref [5]). Also note that the random delay introduced here doesn't necessarily "help" us get a good schedule. All it does is provide us with the necessary conditions under which LLL can be applied, and it can be shown that there does exist an O(c+d) length schedule with a small positive probability.

Amit

It seems like this method could be useful for atleast finding existence of good events if there is less dependence b/w variables. Does this fact somehow could be used to make your algorithm more efficient with better provable bounds?

(Piyush) Note than the less likely the bad events are (i.e. small p), the more willing we are to tolerate dependence (because of the condition ). That is, we can still afford to have a reasonable amount of dependency. For your question on efficient algorithms, refer to Suresh's answer to Nathan's question above.

Also if we try changing the condition; how will it affect the overall analysis?

(Piyush) A weaker condition such as may allow you to tolerate more dependence.

Tilottama

The LLL seems to guaranty a very small probability (even in the best case) for the event being shown to exist.Doesnt this limit its scope of application? Also, it seems to rely on the order of dependency between variables which I guess is inherent to the sampling method or problem.But is there any other method/factor which can be moderated to make the algorithm more efficient and widely applicable?

(Piyush) LLL is especially applicable for proving existence of events that are rare. Finding the bound on dependency depends on the problem structure and I think is possible to come up with such a bound for any problem (ref: Scott's question). For your question on efficient algorithms, refer to Suresh's answer to Nathan's question above.

Arvind

I do not quite follow the analysis of packet routing after we have the expectation of the congestion (c/ac = 1/a).

(Piyush) Since the frame length is log(c), the expected congestion of an edge f in frame F will be (1/a)*log(c). Now we need to find the probability of the event that congestion in an edge is more than log(c). To find this, they apply Chernoff bound with suitably chosen mean μ = log(c) / a and std dev δ = (1 − a) (note that the Chernoff bound looks like Pr(X > (1 + δ)μ) < = F ⁺ (μ,δ)). A union bound is then applied which gives an upper bound on the probabilities of each bad event (i.e. an edge having congestion more than log(c)). Degree of dependency graph is also shown to be bounded by some number. Combining these two facts, we get the desired result from LLL.

Sep 4

Sep 9