Exact Identification of Read-once Formulas Using Fixed Points of Amplification Functions

Authors

Sally A. Goldman, Washington University in St Louis
Michael J. Kearns
Robert E. Schapire

Document Type

Technical Report

Publication Date

1991-06-01

Filename

WUCS-91-38.pdf

Technical Report Number

WUCS-91-38

Abstract

In this paper we describe a new technique for exactly identifying certain classes of read-once Boolean formulas. The method is based on sampling the input-output behavior of the target formula on a probability distribution which is determined by the fixed point of the formula's application function (defined as the probability that a 1 is output by the formula when each input bit is 1 independently with probability p). By performing various statistical tests on easily sampled variants of the fixed-point distribution, we are able to efficiently infer all structural information about any logarithmic-depth formula (with high probability). We apply our results to prove the existence of short universal identification sequences for large classes of formulas. We also describe extensions of our algorithms to handle high rates of noise, and to learn formulas of unbounded depth in Valiant's model with respect to specific distributions.

Comments

Permanent URL: http://dx.doi.org/10.7936/K73T9FKV

Recommended Citation

Goldman, Sally A.; Kearns, Michael J.; and Schapire, Robert E., "Exact Identification of Read-once Formulas Using Fixed Points of Amplification Functions" Report Number: WUCS-91-38 (1991). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/656