One difficulty, of course from the fact that the problem has two things (1) A graph defining the dependence directions (2) A set of constraints which define the distances.

**Wierd question:**Can we make a graph which defines the distances and a set of constraints which define the dependences?

Imagine a network of small nodes (a specific color associated with each nodes of a specific type) with an edge between any two nodes determining the dependence between them.

**question:**what does it mean when CM-Z say that m = O(n^3) or similar things? Do they mean that the graph is a multi-graph? why not?

--

The main intuition of the Megiddo's 1984 paper on LP is driven by Dantzig's observation: there are many redundant constraints. How can we remove the redundant ones fastly?

--

An oracle gives us the depth of the decomposition tree. Let k be the depth of the decomposition tree. How about making O(log k) queries to the oracle and running a scheduler which could run fast assuming that is the depth of the tree?

--

ala fast mat-mul or gaussian elimination when the depth of the decomposition tree is 1??????

--

Start with an example!!!!!! for 1-d sccheduling and one for unitary problem. The 2 node example of KMW with the self edges removed, has decomposition tree of depth 1. Look up the examples in KMW which are similar to this, and have depth 1.