Authors: Richard Beigel and Tirza Hirst
Abstract: Nisan, Rudich, and Saks (FOCS '94) asked whether one help bit can reduce the complexity of computing a boolean function on two inputs in the decision tree model. We prove that one help bit doesn't help. In general, we prove that logk help bits don't help for computing k instances of f. This result is the best possible, since we exhibit functions for which logk + 1 help bits reduce complexity. This shows a gap between 0 and logk + 1 help bits: either f can be evaluated in depth d (the complexity of f) without any help bits, or else logk + 1 help bits are required in order to evaluate k instances in depth d.