{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:27:37Z","timestamp":1763458057593,"version":"3.45.0"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2017,12,26]],"date-time":"2017-12-26T00:00:00Z","timestamp":1514246400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Digiteo France"},{"name":"NSERC of Canada and the \u201cChaire DIGITEO, ENS Cachan - \u00c9cole Polytechnique\u201d"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1217099 and CCF-1524246"],"award-info":[{"award-number":["CCF-1217099 and CCF-1524246"]}],"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. Comput. Theory"],"published-print":{"date-parts":[[2017,3,31]]},"abstract":"<jats:p>\n                    A formulation of\n                    <jats:italic toggle=\"yes\">Ne\u010diporuk\u2019s lower bound method<\/jats:italic>\n                    slightly more inclusive than the usual complexity-measure-specific formulation is presented. Using this general formulation, limitations to lower bounds achievable by the method are obtained for several computation models, such as branching programs and Boolean formulas having access to a sublinear number of nondeterministic bits. In particular, it is shown that any lower bound achievable by the method of Ne\u010diporuk for the size of nondeterministic and parity branching programs is at most\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    <jats:sup>3\/2<\/jats:sup>\n                    \/log\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    ).\n                  <\/jats:p>","DOI":"10.1145\/3013516","type":"journal-article","created":{"date-parts":[[2016,12,27]],"date-time":"2016-12-27T08:51:31Z","timestamp":1482828691000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Nondeterminism and An Abstract Formulation of Ne\u010diporuk\u2019s Lower Bound Method"],"prefix":"10.1145","volume":"9","author":[{"given":"Paul","family":"Beame","sequence":"first","affiliation":[{"name":"University of Washington, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Grosshans","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al and ENS Cachan, Universit\u00e9 Paris-Saclay, Cachan Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al and ENS Cachan, Universit\u00e9 Paris-Saclay, Montr\u00e9al QC, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[{"name":"INRIA and ENS Cachan, Universit\u00e9 Paris-Saclay, Cachan Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,12,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90054-6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","unstructured":"R. B. Boppana and M. Sipser. 1990. The complexity of finite functions. In Handbook of Theoretical Computer Science J. van Leeuwen (Ed.). Vol. A. Elsevier 757--804. 10.1016\/B978-0-444-88071-0.50019-9","DOI":"10.1016\/B978-0-444-88071-0.50019-9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1966.30"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/235767.235769"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702414622"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04650-0"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24508-4"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SCT.1993.336536"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970140004X"},{"key":"e_1_2_1_11_1","first-page":"120","article-title":"A method of circuit synthesis","volume":"1","author":"Lupanov O. B.","year":"1958","unstructured":"O. B. Lupanov. 1958. A method of circuit synthesis. Izv. V.U.Z. Radiofiz. 1 (1958), 120--140.","journal-title":"Izv. V.U.Z. Radiofiz."},{"key":"e_1_2_1_12_1","first-page":"61","article-title":"On the complexity of the realization of the functions of an algebra of logic by formulas","volume":"3","author":"Lupanov O. B.","year":"1960","unstructured":"O. B. Lupanov. 1960. On the complexity of the realization of the functions of an algebra of logic by formulas. Problemy Kibernet. Vyp 3 (1960), 61--80.","journal-title":"Problemy Kibernet. Vyp"},{"key":"e_1_2_1_13_1","unstructured":"W. Masek. 1976. A Fast Algorithm for String Editing Problem and Decision Graph Complexity. Technical Report. Massachussetts Institute of Technology."},{"key":"e_1_2_1_14_1","first-page":"123","article-title":"On the complexity of schemes in some bases containing nontrivial elements with zero weights","volume":"8","year":"1962","unstructured":"\u00c8. Ne\u010diporuk. 1962. On the complexity of schemes in some bases containing nontrivial elements with zero weights. Probl. Kibernet. 8 (1962), 123--160 (in Russian).","journal-title":"Probl. Kibernet."},{"key":"e_1_2_1_15_1","first-page":"765","article-title":"On a boolean function","volume":"169","year":"1966","unstructured":"\u00c8. Ne\u010diporuk. 1966. On a boolean function. Dokl. Acad. USSR 169, 4 (1966), 765--766. Translation: Sov. Math. Dokl. 7, 4 (1966), 999--1000.","journal-title":"Dokl. Acad. USSR"},{"key":"e_1_2_1_16_1","unstructured":"W. Paul. 1978. Komplexit\u00e4tstheorie. Teubner Studienb\u00fccher."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/40997.41003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-54458-5_49"},{"volume-title":"The Complexity of Computing","author":"Savage J. E.","key":"e_1_2_1_19_1","unstructured":"J. E. Savage. 1976. The Complexity of Computing. John Wiley, New York."},{"volume-title":"The Complexity of Boolean Functions. B. G. Teubner 8 John Wiley","author":"Wegener I.","key":"e_1_2_1_20_1","unstructured":"I. Wegener. 1987. The Complexity of Boolean Functions. B. G. Teubner 8 John Wiley, Stuttgart."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719789"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3013516","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3013516","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3013516","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:16:07Z","timestamp":1763457367000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3013516"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,26]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,3,31]]}},"alternative-id":["10.1145\/3013516"],"URL":"https:\/\/doi.org\/10.1145\/3013516","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2016,12,26]]},"assertion":[{"value":"2016-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}