Efficient Linkage Discovery by Limited Probing

Robert B. Heckendorn¹ and Alden H. Wright²

¹University of Idaho,
Moscow, ID 83844-1010 USA,
heckendo@cs.uidaho.edu

²Computer Science,
University of Montana,
Missoula, MT USA,
wright@cs.umt.edu

Abstract. 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.

LNCS 2723, p. 1003 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003