Lower bounds for uniform read-once threshold formulae in the randomized decision tree model

Nikos Leonardos

We investigate the randomized decision tree complexity of a specific class of read-once threshold functions. A read-once threshold formula can be defined by a rooted tree, every in…