Exact identification of read-once formulas using fixed points of amplification functions

Sally A. Goldman, Michael J. Kearns, Robert E. Schapire

Research output: Contribution to journalArticlepeer-review

36 Scopus citations

Abstract

In this paper a new technique is described 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 that is determined by the fixed point of the formula's amplification function (defined as the probability that a one is output by the formula when each input bit is one independently with probability p). By performing various statistical tests on easily sampled variants of the fixed-point distribution, it is possible to efficiently infer all structural information about any logarithmic-depth formula (with high probability). Results are applied to prove the existence of short 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.

Original languageEnglish (US)
Pages (from-to)705-726
Number of pages22
JournalSIAM Journal on Computing
Volume22
Issue number4
DOIs
StatePublished - 1993

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Exact identification of read-once formulas using fixed points of amplification functions'. Together they form a unique fingerprint.

Cite this