Collisions lead to shallower decision trees

James Aspnes, Murat Demirbas, Ryan O'Donnell, Atri Rudra, and Steve Uurtamo. Collisions lead to shallower decision trees. In preparation.

Abstract

We study the following generalization of decision trees, which we call k⁺-decision trees (where k ≥ 1 is an integer). The algorithms are now allowed to query any arbitrary subset of the n input bits and the answer to the query tells if the number of ones in the subset is 0,1,...,k-1 or at least k. We also allow the algorithm to make similar queries for the number of zeroes. Our study of 2⁺-decision trees was motivated by the observation that packet collisions, often considered a nuisance in wireless sensor networks, can be used to reduce the cost of computing aggregate functions of distributed data. The 1⁺ and n⁺-decision trees have connections to combinatorial group testing and a classical problem from combinatorial search respectively.

We show that the deterministic k⁺-decision tree complexity of any boolean function is very closely related to the minimum rank of a decision tree that decides the function. The notion of such a rank has been well studied in the learning literature. We also lower bound the deterministic k⁺-decision tree complexity in terms of the communication complexity of the function and the minimum degree of a polynomial that sign-represents the target function. We study the complexity for threshold functions as well as for the graph connectivity problem.

We also present upper bounds on the zero-error randomized k⁺-decision tree complexity of threshold functions. In the process, we analyze a new ``balls and bins'' problem.

• Rejected SODA 2009 submission: PDF.

BibTeX

@unpublished{AspnesDORU2009,
author = {James Aspnes and Murat Demirbas and Ryan O'Donnell and Atri Rudra and Steve Uurtamo},
title = {Collisions lead to shallower decision trees},
month=june,
year = 2008,
note = "Unpublished manuscript"}