Efficient Linkage Discovery by Limited Probing

Form Invariance and Implicit Parallelism

Robert B. Heckendorn
University of Idaho,
Moscow, ID 83844-1010 ~USA,
heckendo@cs.uidaho.edu,

Alden H. Wright
Computer Science Dept.
Univ. of Montana
Missoula, MT 59812
wright@cs.umt.edu
(406) 243-4790
http://www.cs.umt.edu/u/wright/wright.htm

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.