{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:24:44Z","timestamp":1787509484679,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2006,5,21]],"date-time":"2006-05-21T00:00:00Z","timestamp":1148169600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2006,5,21]]},"DOI":"10.1145\/1132516.1132569","type":"proceedings-article","created":{"date-parts":[[2006,7,24]],"date-time":"2006-07-24T12:53:01Z","timestamp":1153745581000},"page":"363-372","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Hardness of approximate two-level logic minimization and PAC learning with membership queries"],"prefix":"10.1145","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[{"name":"Harvard University, Cambridge, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,5,21]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-005-1396-1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.36"},{"key":"e_1_3_2_1_3_1","volume-title":"Nov","author":"Allender E.","year":"2005","unstructured":"E. Allender , L. Hellerstein , P. McCabe , T. Pitassi , and M. Saks . Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Electronic Colloquium on Computational Complexity (ECCC), (126) , Nov , 2005 .]] E. Allender, L. Hellerstein, P. McCabe, T. Pitassi, and M.Saks. Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Electronic Colloquium on Computational Complexity (ECCC), (126), Nov, 2005.]]"},{"key":"e_1_3_2_1_4_1","volume-title":"On the complexity of finding minimal representations of boolean functions","author":"Allender E.","year":"2004","unstructured":"E. Allender , L. Hellerstein , T. Pitassi , and M. Saks . On the complexity of finding minimal representations of boolean functions . 2004 . Unpublished .]] E. Allender, L. Hellerstein, T. Pitassi, and M.Saks. On the complexity of finding minimal representations of boolean functions. 2004. Unpublished.]]"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1026"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167174"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1075"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0893-6080(05)80010-3"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/24.285125"},{"key":"e_1_3_2_1_10_1","volume-title":"Two-level logic minimization","author":"Coudert O.","year":"2001","unstructured":"O. Coudert and T. Sasao . Two-level logic minimization . Kluwer Academic Publishers , 2001 .]] O. Coudert and T. Sasao. Two-level logic minimization. Kluwer Academic Publishers, 2001.]]"},{"key":"e_1_3_2_1_11_1","volume-title":"The complexity of minimizing disjunctive normal form formulas. Master's thesis","author":"Czort S.","year":"1999","unstructured":"S. Czort . The complexity of minimizing disjunctive normal form formulas. Master's thesis , University of Aarhus , 1999 .]] S. Czort. The complexity of minimizing disjunctive normal form formulas. Master's thesis, University of Aarhus, 1999.]]"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704443057"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02772959"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/791229.792251"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/PGEC.1965.264175"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(78)90562-4"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a007"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509976"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1533"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1964.1053689"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28426"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380809"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/40.988690"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"e_1_3_2_1_26_1","volume-title":"Some NP-complete set covering problems. unpublished","author":"Masek W.","year":"1979","unstructured":"W. Masek . Some NP-complete set covering problems. unpublished , 1979 .]] W. Masek. Some NP-complete set covering problems. unpublished, 1979.]]"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1956.tb03835.x"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/646341.686722"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289615"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/48014.63140"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1952.11988183"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1955.11988710"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258641"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00043-9"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380839"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1775"},{"key":"e_1_3_2_1_39_1","volume-title":"Lecture notes on pseudorandomness.","author":"Vadhan S.","year":"2004","unstructured":"S. Vadhan . Lecture notes on pseudorandomness. Available at http:\/\/www.courses.fas.harvard.edu\/~cs225\/, 2004 .]] S. Vadhan. Lecture notes on pseudorandomness. Available at http:\/\/www.courses.fas.harvard.edu\/~cs225\/, 2004.]]"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"e_1_3_2_1_41_1","first-page":"560","volume-title":"Proceedings of the Ninth International Joint Conference on Artificial Intelligence","author":"Valiant L.","year":"1985","unstructured":"L. Valiant . Learning disjunctions of conjunctions . In Proceedings of the Ninth International Joint Conference on Artificial Intelligence , pages 560 -- 566 , 1985 .]] L. Valiant. Learning disjunctions of conjunctions. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, pages 560--566, 1985.]]"}],"event":{"name":"STOC06: Symposium on Theory of Computing","location":"Seattle WA USA","acronym":"STOC06","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132569","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1132516.1132569","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:18:50Z","timestamp":1750249130000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1132516.1132569"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,5,21]]},"references-count":40,"alternative-id":["10.1145\/1132516.1132569","10.1145\/1132516"],"URL":"https:\/\/doi.org\/10.1145\/1132516.1132569","relation":{},"subject":[],"published":{"date-parts":[[2006,5,21]]},"assertion":[{"value":"2006-05-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}