On read-once threshold formulae and their randomized decision tree complexity
R. Heiman, Ilan Newman, Avi Wigderson · 2002
TC/sup 0/ is the class of functions computable by polynomial-size, constant-depth formulae with threshold gates. Read-once TC/sup 0/ (RO-TC/sup 0/) is the subclass of TC/sup 0/ which restricts every variable to exactly one occurrence in the formula. The main result is a tight linear lower bound on the randomized decision tree complexity of any function in RO-TC/sup 0/. This relationship between threshold circuits and decision trees bears significance on both models of computation. Regarding decision trees, this is the first class of functions for which such a strong bound is known. Regarding threshold circuits, it may be considered as a possible first step toward proving TC/sup 0/ not=NC/sup 1/; generalizing the lower bound to all functions in TC/sup 0/ will establish this separation. Another structural result is that a read-once threshold formula uniquely represents the function it computes.>