Exact identification of circuits using fixed points of amplification functions

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

Research output: Contribution to journalConference article

1 Scopus citations

Abstract

A technique for exactly identifying certain classes of read-once Boolean formulas is introduced. 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 amplification 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, it is possible to infer efficiently all structural information about any logarithmic-depth target family (with high probability). The results are used to prove the existence of short universal identification sequences for large classes of formulas. Extensions of the algorithms to handle high rates of noise and to learn formulas of unbounded depth in L. G. Valiant's (1984) model with respect to specific distributions are described.

Original languageEnglish (US)
Pages (from-to)193-202
Number of pages10
JournalIEEE Transactions on Industry Applications
Volume27
Issue number1 pt 1
StatePublished - Jan 1 1991
Externally publishedYes
Event1989 Industry Applications Society Annual Meeting - San Diego, CA, USA
Duration: Oct 1 1989Oct 5 1989

All Science Journal Classification (ASJC) codes

  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering
  • Electrical and Electronic Engineering

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

  • Cite this