Two interesting comparisons Comparison to decision tree: Decision tree complexity:make the longest path short Here:make the shortest path long. Comparison to VC-dim lower bound: [Thm]The value is exactly the extensive equivalence query complexity. -A measure in learning theory. Strengthen the VC-dim lower bound by NayakTwo interesting comparisons • Comparison to decision tree: – Decision tree complexity: make the longest path short – Here: make the shortest path long. • Comparison to VC-dim lower bound: [Thm] The value is exactly the extensive equivalence query complexity. – A measure in learning theory. – Strengthen the VC-dim lower bound by Nayak