{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:19Z","timestamp":1787340859720,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1993,8]]},"abstract":"<jats:p>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\u2019s 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\u2019s model with respect to specific distributions.<\/jats:p>","DOI":"10.1137\/0222047","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:38:56Z","timestamp":1109227136000},"page":"705-726","source":"Crossref","is-referenced-by-count":34,"title":["Exact Identification of Read-Once Formulas Using Fixed Points of Amplification Functions"],"prefix":"10.1137","volume":"22","author":[{"given":"Sally A.","family":"Goldman","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael J.","family":"Kearns","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Robert E.","family":"Schapire","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138061"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022873112823"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(91)90026-X"},{"key":"R4","first-page":"27","volume-title":"Advances in Computing Research 5: Randomness and Computation","author":"Benedek G. M.","year":"1989"},{"key":"R5","unstructured":"G. M. Benedek, A. Itai, Ph.D. Thesis,  Lower hounds for monotone circuits and formulas, Massachusetts Institute of Technology, Cambridge, MA,  1986"},{"key":"R6","unstructured":"N. Bshouty, T. Hancock, L. Hellerstein, M. Karpinski,  Read-once formulas, justifying assignments, and generic transformations,  1991, unpublished manuscript"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"M. Furst, J. Jackson, S. Smith,  Improved learning of  $AC^0$ functions,  Proceedings of the Fourth Annual Workshop on Computational Learning Theory,  1991,  317\u2013325, Aug.","DOI":"10.1016\/B978-1-55860-213-7.50032-8"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"S. A. Goldman, M. J. Kearns,  On the complexity of teaching,  Proceedings of the Fourth Annual Workshop on Computational Learning Theory,  1991,  303\u2013314, Aug.","DOI":"10.1016\/B978-1-55860-213-7.50031-6"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"T. Hancock, L. Hellerstein,  Learning read-once formulas over fields and extended bases,  Proceedings of the Fourth Annual Workshop on Computational Learning Theory,  1991,  326\u2013336, Aug.","DOI":"10.1016\/B978-1-55860-213-7.50033-X"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"T. Hancock, Y. Mansour,  Learning monotone  $k\\mu$ DNF formulas on product distributions,  Proceedings of the Fourth Annual Workshop on Computational Learning Theory,  1991,  179\u2013183, Aug.","DOI":"10.1016\/B978-1-55860-213-7.50020-1"},{"key":"R11","unstructured":"L. Hellerstein, Ph.D. Thesis,  On characterizing and learning some classes of read-once formulas, University of California, Berkeley, CA,  1989 0207.36902"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"R13","volume-title":"The Computational Complexity of Machine Learning","author":"Kearns J.","year":"1990"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"M. Kearns, M. Li,  Learning in the presence of malicious errors,  Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing,  1988,  267\u2013280, May","DOI":"10.1145\/62212.62238"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Kearns, M. Li, L. Pitt, L. Valiant,  On the learnahility of Boolean fomulae,  Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing,  1987,  285\u2013295, May","DOI":"10.1145\/28395.28426"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"M. Kearns, L. G. Valiant,  Cryptographic limitations on learning Boolean formulae and finite automata, in Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, May 1989, pp. 433\u2013444; J. Assoc. Comput. Mach., to appear","DOI":"10.1145\/73007.73049"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"N. Linial, Y. Mansour, N. Nisan,  Constant depth circuits, Fourier transform, and learnahility,  Proceedings of the 30th Annual Symposium on Foundations of Computer Science,  1989,  574\u2013579, Oct.","DOI":"10.1109\/SFCS.1989.63537"},{"key":"R18","unstructured":"G. Pagallo, D. Haussler,  A greedy method for learning  $\\mu$ DNF functions under the uniform distribution, Tech. Report, UCSC-CRL-89-12, Computer Research Laboratory, University of California, Santa Cruz, CA,  1989, June"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(90)90028-J"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022648800760"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"R. E. Schapire,  Learning probabilistic read-once formulas on product distributions, in Proceedings of the Fourth Annual Workshop on Computational Learning Theory, Aug. 1991, pp. 184\u2013198, Machine Learning, to appear","DOI":"10.1016\/B978-1-55860-213-7.50021-3"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037091"},{"key":"R23","unstructured":"Robert Sloan,  Types of noise in data for concept learning (extended abstract),  Proceedings of the 1988 Workshop on Computational Learning Theory (Cambridge, MA, 1988), Morgan Kaufmann, San Mateo, CA,  1989,  91\u201396, Aug. 1 109 726"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"K. Verbeurgt,  Learning DNF under the uniform distribution in quasi-polynomial time,  Proceedings of the Third Annual Workshop on Computational Learning Theory,  1990,  314\u2013326, Aug.","DOI":"10.1016\/B978-1-55860-146-8.50027-8"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0222047","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:52:50Z","timestamp":1787338370000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0222047"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,8]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1993,8]]}},"alternative-id":["10.1137\/0222047"],"URL":"https:\/\/doi.org\/10.1137\/0222047","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,8]]}}}