{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:33Z","timestamp":1750220973471,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T00:00:00Z","timestamp":1559865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["1547360"],"award-info":[{"award-number":["1547360"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,7,31]]},"abstract":"<jats:p>\n            Given a drawing of a read-once formula (called the blueprint), and a blackbox implementation with the same topology as the blueprint that purports to compute the formula, can we tell if it does? Under a fault model, where the only faults in the implementation are gates that complement their outputs, we show that there is an efficient algorithm that makes a linear number of probes to the blackbox implementation and determines if the blueprint and implementation are identical. We also show a matching lower bound. We further ask whether we can diagnose where the faults are, using blackbox testing. We prove that if the implementation has a property called\n            <jats:italic>polynomial balance<\/jats:italic>\n            , then it is possible to do this efficiently. To complement this result, we show that even if the\n            <jats:italic>blueprint<\/jats:italic>\n            is polynomially balanced and there are only logarithmically many errors in the implementation, the implementation could be unbalanced and the diagnosis problem provably requires super-polynomially many tests. We point out that this problem is one instance of a general class of problems of learning deviations from a blueprint, which we call\n            <jats:italic>conformance learning<\/jats:italic>\n            . Conformance learning seems worthy of further investigation in a broader context.\n          <\/jats:p>","DOI":"10.1145\/3313776","type":"journal-article","created":{"date-parts":[[2019,6,10]],"date-time":"2019-06-10T12:10:51Z","timestamp":1560168651000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Locating Errors in Faulty Formulas"],"prefix":"10.1145","volume":"15","author":[{"given":"Sampath","family":"Kannan","sequence":"first","affiliation":[{"name":"University of Pennsylvania, Walnut St. Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9876-3991","authenticated-orcid":false,"given":"Kevin T.","family":"Tian","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Walnut St. Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,6,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/138027.138061"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404042"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1042"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366827"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.818405"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.30978"},{"volume-title":"Logic Testing and Design for Testability","author":"Fujiwara Hideo","key":"e_1_2_1_7_1","unstructured":"Hideo Fujiwara . 1985. Logic Testing and Design for Testability . MIT Press , Cambridge, MA . Hideo Fujiwara. 1985. Logic Testing and Design for Testability. MIT Press, Cambridge, MA."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.312190"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222047"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.75261"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.41"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.2628"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90062-2"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022646704993"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"volume-title":"Probabilistic logics and the synthesis of reliable organisms from unreliable components","author":"von Neumann J.","key":"e_1_2_1_16_1","unstructured":"J. von Neumann . 1956. Probabilistic logics and the synthesis of reliable organisms from unreliable components . Automata Studies, C. Shannon (Ed.), Vol. 34 . Princeton Univ. Press , 43--98. J. von Neumann. 1956. Probabilistic logics and the synthesis of reliable organisms from unreliable components. Automata Studies, C. Shannon (Ed.), Vol. 34. Princeton Univ. Press, 43--98."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313776","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313776","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313776","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:33Z","timestamp":1750204473000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313776"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,7]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,7,31]]}},"alternative-id":["10.1145\/3313776"],"URL":"https:\/\/doi.org\/10.1145\/3313776","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2019,6,7]]},"assertion":[{"value":"2018-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-06-07","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}