**The Hardness of the Expected
Decision Depth Problem**

Dana Ron, Amir Rosenfeld, and Salil
Vadhan

### Abstract

Given a function f over n binary variables, and an ordering
of the n variables, we consider the Expected Decision Depth problem. Namely,
what is the expected number of bits that need to be observed until the value of
the function is determined, when bits of the input are observed according to
the given order. Our main finding is that this problem is (essentially)
#P-complete. Moreover, the hardness holds even when the function f is
represented as a decision tree.

### Versions

·
*Information
Processing Letters,* 101(3):112-118, 2007. [pdf][IPL page]

[ back to
Salil Vadhan's research]