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

Video Recording