James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, and Steve Uurtamo.
k^{+} decision trees.
Sixth International Workshop on Algorithms for Sensor Systems, Revised Selected Papers,
Lecture Notes in Computer Science 6451,
Springer-Verlag, July 2010, pp. 74–88.

Consider a wireless sensor network in which each sensor has a bit of information. Suppose all sensors with the bit 1 broadcast this fact to a basestation. If zero or one sensors broadcast, the basestation can detect this fact. If two or more sensors broadcast, the basestation can only detect that there is a "collision." Although collisions may seem to be a nuisance, they can in some cases help the basestation compute an aggregate function of the sensors' data.

Motivated by this scenario, we study a new model of computation for
boolean functions: the *2 ^{+} decision tree*. This model is an
augmentation of the standard decision tree model: now each internal
node queries an arbitrary

Our main result shows that 2^{+} decision trees can "count" rather
effectively. Specifically, we show that zero-error 2^{+} decision
trees can compute the threshold-of-t symmetric function with O(t)
expected queries (and that Ω(t) is a lower bound even for
two-sided error 2^{+} decision trees). Interestingly, this feature is
not shared by 1^{+} decision trees. Our result implies that the
natural generalization to k^{+} decision trees does not give much
more power than 2^{+} decision trees. We also prove a lower bound of
Ω~(t⋅log(n/t)) for the *deterministic* 2^{+}
complexity of the threshold-of-t function, demonstrating that the
randomized 2^{+} complexity can in some cases be unboundedly better
than deterministic 2^{+} complexity.

Finally, we generalize the above results to arbitrary symmetric
functions, and we discuss the relationship between k^{+} decision
trees and other complexity notions such as decision tree rank and
communication complexity.

- ALGOSENSORS 2010 proceedings version:
**PDF**.

@inproceedings{AspnesBDORU2010, author = {James Aspnes and Eric Blais and Murat Demirbas and Ryan O'Donnell and Atri Rudra and Steve Uurtamo}, title = {$k^+$ decision trees}, month=jul, year = 2010, booktitle={Algorithms for Sensor Systems: 6th International Workshop on Algorithms for Sensor Systems, Wireless Ad Hoc Networks, and Autonomous Mobile Entities, ALGOSENSORS 2010, Bordeaux, France, July 5, 2010, Revised Selected Papers}, publisher = {Springer-Verlag}, series = {Lecture Notes in Computer Science}, volume = 6451, pages = {74--88} }

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page