## 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 language | English (US) |
---|---|

Pages (from-to) | 193-202 |

Number of pages | 10 |

Journal | IEEE Transactions on Industry Applications |

Volume | 27 |

Issue number | 1 pt 1 |

State | Published - Jan 1991 |

Externally published | Yes |

Event | 1989 Industry Applications Society Annual Meeting - San Diego, CA, USA Duration: Oct 1 1989 → Oct 5 1989 |

## All Science Journal Classification (ASJC) codes

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