**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 log*k* help bits don't help for computing
*k* instances of *f*. This result is the best possible,
since we exhibit functions for which log*k* + 1 help bits reduce
complexity. This shows a gap between 0 and log*k* + 1 help bits:
either *f* can be evaluated in depth *d* (the complexity of
*f*) without any help bits, or else log*k* + 1 help bits are
required in order to evaluate *k* instances in depth *d*.