Information equivalence simplifies decision tree size and success rates
The Information Complexity of Decision Trees
Computational Complexity
Summary
Decision trees are a way computers make choices step-by-step. The authors studied how much information is really needed to make these decisions when randomness is involved. They found that the information needed matches exactly how big the tree must be when solving many problems at once. Their work also shows you can make decision trees smaller if you accept a small chance of error. Additionally, they proved a property that helps understand how solving many problems together affects information needs.
What this means in practice
- •For algorithm designers: Optimize decision tree algorithms by compressing tree size based on information complexity without much loss in accuracy.
- •For complexity theorists: Use the perfect direct product theorem in information complexity to analyze success rates in batch randomized computations.
A theory result. No direct application yet.
Authors
Avantika Agarwal, Shalev Ben-David, Eric Blais
Abstract
We define and study a measure of information complexity for randomized decision trees. We prove three main results about this complexity measure: Information equals amortized size complexity. We show that the information complexity of randomized decision tree is equal to the logarithm of the amortized worst-case randomized tree size complexity of computing a function f. That is, when computing f on n inputs, the logarithm of the randomized tree size is exactly equal to the amount of information needed to compute the function. Information allows for tree size compression. We show that even when computing f on a single input, the information complexity can be used to compress the size of a tree, if we allow a small loss in success probability. With the recent characterization of Chattopadhyay, Dahiya, Mande, Radhakrishnan, and Sanyal (2023), this result shows that the depth of AND-OR trees can also be compressed in terms of information complexity. Direct Product Theorems. We show that the success-conditioned variant of information complexity satisfies a perfect direct product theorem. This result gives an information complexity analogue of the direct product theorem for success-conditioned randomized query complexity by Ben-David and Blais (2025).