Testing and Reconstruction via Decision Trees

          @misc{ scivideos_16889,
            doi = {},
            url = {https://simons.berkeley.edu/talks/tbd-261},
            author = {},
            keywords = {},
            language = {en},
            title = {Testing and Reconstruction via Decision Trees},
            publisher = {The Simons Institute for the Theory of Computing},
            year = {2020},
            month = {dec},
            note = {16889 see, \url{https://scivideos.org/Simons-Institute/16889}}
          }
          

Abstract

We study sublinear and local computation algorithms for decision trees, focusing on the related tasks of testing and reconstruction.  In testing, we would like to determine if an unknown function $f$ is close to a size-$s$ decision tree.  In reconstruction, we are given query access to a function $f$ that is promised to be close to a size-$s$ decision tree, and we would like to provide "on-the-fly" query access to a decision tree, ideally of size not much larger than $s$, that is close to $f$.   We give the first reconstruction algorithm for decision trees, and from it we derive a new tester for decision trees.  By known relationships, our results yield reconstruction algorithms for numerous other boolean function properties---Fourier degree, randomized and quantum query complexities, certificate complexity, sensitivity, etc.---which in turn yield new testers for these properties. Joint work with Guy Blanc (Stanford) and Jane Lange (MIT).