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.