License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2022.17
URN: urn:nbn:de:0030-drops-158273
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15827/
Go to the corresponding LIPIcs Volume Portal

Bshouty, Nader H. ; Haddad-Zaknoon, Catherine A.

On Testing Decision Tree

pdf-format:
LIPIcs-STACS-2022-17.pdf (0.7 MB)

Abstract

In this paper, we study testing decision tree of size and depth that are significantly smaller than the number of attributes n.
Our main result addresses the problem of poly(n,1/ε) time algorithms with poly(s,1/ε) query complexity (independent of n) that distinguish between functions that are decision trees of size s from functions that are ε-far from any decision tree of size ϕ(s,1/ε), for some function ϕ > s. The best known result is the recent one that follows from Blanc, Lange and Tan, [Guy Blanc et al., 2020], that gives ϕ(s,1/ε) = 2^{O((log³s)/ε³)}. In this paper, we give a new algorithm that achieves ϕ(s,1/ε) = 2^{O(log² (s/ε))}.
Moreover, we study the testability of depth-d decision tree and give a distribution free tester that distinguishes between depth-d decision tree and functions that are ε-far from depth-d² decision tree.

BibTeX - Entry

@InProceedings{bshouty_et_al:LIPIcs.STACS.2022.17,
  author =	{Bshouty, Nader H. and Haddad-Zaknoon, Catherine A.},
  title =	{{On Testing Decision Tree}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15827},
  URN =		{urn:nbn:de:0030-drops-158273},
  doi =		{10.4230/LIPIcs.STACS.2022.17},
  annote =	{Keywords: Testing decision trees}
}

Keywords: Testing decision trees
Collection: 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Issue Date: 2022
Date of publication: 09.03.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI