Efficient Linkage Discovery by Limited Probing
Form Invariance and Implicit Parallelism
Robert B. Heckendorn
University of Idaho,
Moscow, ID 83844-1010 ~USA,
Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
This paper addresses the problem of determining the epistatic linkage
of a function from binary strings to the reals. There is a close relationship
between the Walsh coefficients of the function and "probes" (or perturbations)
of the function. This relationship leads to two linkage detection
algorithms that generalize earlier algorithms of the same type.
A rigorous complexity analysis is given of the first algorithm.
The second algorithm not only detects the epistatic linkage, but
also computes all of the Walsh coefficients. This algorithm
is much more efficient than previous algorithms for the same purpose.