k⁺ decision trees

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.

Abstract

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 set of literals and branches on whether 0, 1, or at least 2 of the literals are true. This model was suggested in a work of Ben-Asher and Newman but does not seem to have been studied previously.

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.

BibTeX

@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}
}