0
$\begingroup$

I am trying to understand what an algebraic decision tree is but wikipedia lacks a formal definition, just an intuition. So I need to check if my understanding is correct.

From what I have read it seems that an algebraic decision tree is:

  • A tree where each node has exactly 2 children.
  • Each node in the tree is a polynomial function of degree at most $n$, that takes a vector of size $n$ and returns the sign of the polynomial.
  • Given an input vector we evaluate the polynomial at the root node, then if the sign is positive we evaluate the polynomial of the right child otherwise that of the left.
  • We do this until we hit a leaf node.

Is the above description correct?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Wikipedia is not a primary source. It cites references that it says define this model. Have you read those primary sources? Can you summarize what you've found? $\endgroup$
    – D.W. ♦
    Oct 10, 2022 at 0:16
  • $\begingroup$ See lecture notes of Jeff Erickson. $\endgroup$
    – Yuval Filmus
    Oct 10, 2022 at 21:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.