Metraipolis › archive › dc_7213fbad3fbf

The Information Complexity of Decision Trees — arXiv:2609.12164

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.12164
License (as archived)
CC0-1.0
Archived
2026-10-16T03:59:21.887Z
SHA-256 of the archived text
0b23aab42e50ef75a49038396d1e77f8f75b2bcb78a4ed566307521869e96f86
Stable URL of this page
https://metraipolis.com/documento/dc_7213fbad3fbf

How to cite

The Information Complexity of Decision Trees — arXiv:2609.12164 — arXiv (en), https://arxiv.org/abs/2609.12164 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7213fbad3fbf (Metraipolis archive dc_7213fbad3fbf, sha256 0b23aab42e50ef75a49038396d1e77f8f75b2bcb78a4ed566307521869e96f86)
BibTeX
@misc{dc7213fbad3fbf,
  title = {The Information Complexity of Decision Trees — arXiv:2609.12164},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.12164},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7213fbad3fbf; sha256 0b23aab42e50ef75a49038396d1e77f8f75b2bcb78a4ed566307521869e96f86},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.12164. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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).

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-14 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.12164 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T03:50:48.480Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).