This work addresses the problem of discovering the structure of a function from fixed length binary strings to the nonnegative reals when the function is given as a black box. The function is assumed to be a sum of component functions, where each component function depends on at most k bits (where k is less than the string length). An algorithm is given that finds the complete structure of the given function by sampling function values. Under the assumption that k is constant and that the number of component functions grows linearly with the string length, the complexity of this algorithm is shown to be function evaluations where L is the string length.

(This is joint work with Robert Heckendorn, Department of Computer Science, University of Idaho).