Bounding the randomized decision tree complexity of read-once Boolean functions
Kazuyuki Amano · 2011
We investigate the deterministic and the randomized decision tree complexities of Boolean functions, denoted by D(f) and R(f), respectively. A long standing conjecture is that, for every Boolean) function f, R(f) =