**Problem Detail:**

Say that we have nodes in a tree and it has a branching factor of 3. At the leaves we have a binary value 1 or 0 (which can be viewed as "votes"). Each parent computes the majority of its children and assigns itself that value ("vote").

What I want to show is that in the worst case, a deterministic algorithm will have to query the value of all of the $n = 3^h$ leaves in order to determine the value assigned to the root.

I do have the following solution which I am having a hard time understanding:

But that algorithm doesn't seem to work in some trivial cases (unless I misunderstood the algorithm).

Say that A just started querying the leaves. So it queries the first leaf and since nothing has been assigned, when it goes to its first ancestor such that at most 1 is determined, since none of his siblings (which in this case are the siblings of the parent of the leaf, the uncles) have been determine, then that leaf is arbitrarily assigned true. When it goes to the next leaf, one should assign it false so that one has to inspect the other leaf, but when if you follow what the adversarial algorithm does it doesn't work. It says to go to the parent of the currently queried leaf and in this case, since still, none of the siblings of the parent have been assigned anything, then one would arbitrarily choose true, which is bad, because it determines the parent to be true without looking at the last leaf node of that subsection!

I am wrong or am I misunderstanding what $B$ is suppose to do?

Why isn't it just optimal to always choose 1 0 1 or 0 1 0 or 1 1 0 or however A queries leaves, to make sure that it always sees two leaf, such that it has to see the other leaf no matter what (i.e. if A sees a 1 to make sure the next thing it sees in that sub section of the leafs to see a 0 etc). I don't understand why we need to consider ancestors. Why does that matter?

For completeness I will provide the full text:

###### Asked By : Charlie Parker

###### Answered By : Yuval Filmus

Yes, you are misunderstanding the algorithm. While I explain your misunderstanding below, in general, when such a misunderstanding occurs, see if you understand what the algorithm is trying to do, and then try to match your understanding with what is written.

While there are numerous errors in textbooks, usually they are slight and easy to correct. Whenever an error seems to have occurred (which doesn't seem to be the case here), see if you can try to correct it by making some small change to the argument.

In this case, the first ancestor of the second leaf which has at most one sibling determined is the leaf itself, which has one sibling determined. According to the strategy, our answer to the second leaf would be complementary to our answer to the first leaf.

Your misunderstanding might stem from the fact that for you a node is not considered its own ancestor. However, for this strategy to work, a node must be considered its own ancestor, as your example shows. Presumably the text defined ancestor correctly to include the node itself, but even if it doesn't you could correct the proof by changing slightly the meaning of ancestor. This demonstrates my points above regarding reading mathematical texts.

Question Source : http://cs.stackexchange.com/questions/49048

**3200 people like this**

## 0 comments:

## Post a Comment

Let us know your responses and feedback