k+ Decision Trees
Eric Blais
Jan 20, 2010
ABSTRACT: Consider a wireless sensor network in which a central node broadcasts a message asking the sensor nodes to respond if their local temperature exceeds a fixed threshold. If 2 or more sensor nodes reply simultaneously, then a collision is detected at the central node. Collisions are typically regarded as a nuisance, and much effort has been spent on devising network protocols that avoid them. We take a different approach, and instead study how the information provided by collisions may be used to compute functions more efficiently. We do so in the model of k+ decision trees. In a k+ decision tree, the internal nodes query a set of literals and branch on whether 0, 1, 2, ..., k-1, or at least k literals are satisfied. (The wireless sensor network scenario described above corresponds to the 2+ decision tree model.) In the talk, we will examine basic structural results on k+ decision trees that show how this model is qualitatively different than the standard decision tree model, and show how some functions can be computed much more efficiently by k+ decision trees than standard decision trees. This talk is based on joint work with James Aspnes, Murat Demirbas, Ryan O'Donnell, Atri Rudra, and Steve Uurtamo.