James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra and Steve Uurtamo

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

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.