Sa. Goldman et al., EXACT IDENTIFICATION OF READ-ONCE FORMULAS USING FIXED-POINTS OF AMPLIFICATION FUNCTIONS, SIAM journal on computing, 22(4), 1993, pp. 705-726
In this paper a new technique is described for exactly identifying cer
tain classes of read-once Boolean formulas. The method is based on sam
pling the input-output behavior of the target formula on a probability
distribution that is determined by the fixed point of the formula's a
mplification function (defined as the probability that a one is output
by the formula when each input bit is one independently with probabil
ity p). By performing various statistical tests on easily sampled vari
ants of the fixed-point distribution, it is possible to efficiently in
fer all structural information about any logarithmic-depth formula (wi
th high probability). Results are applied to prove the existence of sh
ort universal identification sequences for large classes of formulas.
Also described are extensions of these algorithms to handle high rates
of noise, and to learn formulas of unbounded depth in Valiant's model
with respect to specific distributions.