--
If we generalize the idea of the oracle further and say that we can verify in some time T \in POLY(n,m,d,max-distance), whether the KMW-T has depth is k or not. Suppose an oracle tells us that the depth of the KMW-T is <= k. A (binary?) search across k would give us the certificate to verify the statement. This would take the running time of the algorithm to be T * log k. How can we do better?
--
to do:
--
Prime and composite nodes: In the previous post, there were a couple of analogies between the different decomposition trees. Let us call a leaf of a decomposition tree prime, if it is annotated with a component which is a node of the original graph. Otherwise, call the leaf as composite. The whole problem of ZC-detection is but seeing if there exists a composite node.
--
Define an edge casting a shadow on another component if the edge is in the maximal independent subspace of the component????? So, can we begin with a node and keep adding edges to it till we detect a ZC?
--
To do: get the idea of maximal independent subspace and difference between the witness and certificate of CM-Z.
--
Top-down decomposition Vs. Bottom-up construction: How to unify two components?
--
To-do: understand the KMW-EX with depth of 1 and 2. how and why are the depths of that size.
to-do: frame a LP program which takes a two connected components and returns a parent node with a certificate. Suppose we want to add a third node which is in the same strongly connected component as these two, it need not have a parent which is different from these two. It can be attached to the same parent as the original. The certificate stored at the parent may or maynot change.
--
The KMW-EX -577 is very useful to know about the longest paths. Visalize a bounding box, with nodes of two colors and the dependences. If there is a circuit in G^\infty, there is a loop in the PRDG.
--
The memory optimization by building through subspaces and simultaneously increasing the "range" of subspaces.
Posts
