Checking Tests for Read-Once Functions over Arbitrary Bases
  A Boolean function is called read-once over a basis B if it can be expressed
by a formula over B where no variable appears more than once. A checking test
for a read-once function f over B depending on all its variables is a set of
input vectors distinguishing f from all other read-once functions of the same
variables. We show that every read-once function f over B has a checking test
containing O(n^l) vectors, where n is the number of relevant variables of f and
l is the largest arity of functions in B. For some functions, this bound cannot
be improved by more than a constant factor. The employed technique involves
reconstructing f from its l-variable projections and provides a stronger form
of Kuznetsov's classic theorem on read-once representations.
