{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:20:37Z","timestamp":1771485637741,"version":"3.50.1"},"reference-count":14,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T00:00:00Z","timestamp":1543276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"name":"JSPS KAKENHI","award":["26730007 and 25240002"],"award-info":[{"award-number":["26730007 and 25240002"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2019,3,31]]},"abstract":"\n Toward the ultimate goal of separating\n L<\/jats:bold>\n and\n P<\/jats:bold>\n , Cook, McKenzie, Wehr, Braverman, and Santhanam introduced the\n Tree Evaluation Problem<\/jats:italic>\n (\n TEP<\/jats:italic>\n ). For fixed integers\n h<\/jats:italic>\n and\n k<\/jats:italic>\n > 0,\n \n FT\n h<\/jats:sub>\n <\/jats:italic>\n (\n k<\/jats:italic>\n ) is given as a complete, rooted binary tree of height\n h<\/jats:italic>\n , in which each root node is associated with a function from [\n k<\/jats:italic>\n ]\n 2<\/jats:sup>\n to [\n k<\/jats:italic>\n ], and each leaf node with a number in [\n k<\/jats:italic>\n ]. The value of an internal node\n v<\/jats:italic>\n is defined naturally; that is, if it has a function\n f<\/jats:italic>\n and the values of its two child nodes are\n a<\/jats:italic>\n and\n b<\/jats:italic>\n , then the value of\n v<\/jats:italic>\n is\n f<\/jats:italic>\n (\n a<\/jats:italic>\n ,\n b<\/jats:italic>\n ). Our task is to compute the value of the root node by sequentially executing this function evaluation in a bottom-up fashion. The problem is obviously in\n P<\/jats:bold>\n , and, if we could prove that any branching program solving\n \n FT\n h<\/jats:sup>\n <\/jats:italic>\n (\n k<\/jats:italic>\n ) needs at least\n k<\/jats:italic>\n \n r<\/jats:italic>\n (\n h<\/jats:italic>\n )\n <\/jats:sup>\n states for any unbounded function\n r<\/jats:italic>\n , then this problem is not in\n L<\/jats:bold>\n , thus achieving our goal. The mentioned authors introduced a restriction called\n thrifty<\/jats:italic>\n against the structure of BP\u2019s (i,e., against the algorithm for solving the problem) and proved that any thrifty BP needs \u03a9(\n \n k\n h<\/jats:sup>\n <\/jats:italic>\n ) states. This article proves a similar lower bound for\n read-once<\/jats:italic>\n branching programs, which allows us to get rid of the restriction on the order of nodes read by the BP that is the nature of the thrifty restriction.\n <\/jats:p>","DOI":"10.1145\/3282433","type":"journal-article","created":{"date-parts":[[2018,11,27]],"date-time":"2018-11-27T13:18:59Z","timestamp":1543324739000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Read-Once Branching Programs for Tree Evaluation Problems"],"prefix":"10.1145","volume":"11","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[{"name":"RIMS, Kyoto University, Kitashirakawa-Oiwakecho, Sakyo-ku, Kyoto, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Atsuki","family":"Nagao","sequence":"additional","affiliation":[{"name":"The University of Electro-Communications, Chofu, Tokyo, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,11,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12134"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2077336.2077337"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9049-y"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(98)00042-0"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00323-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2751320"},{"key":"e_1_2_1_9_1","first-page":"765","article-title":"A Boolean function","volume":"169","year":"1998","unstructured":"\u00c8. Ne\u010diporuk. 1998 . A Boolean function . In Doklady of the Academy of the USSR , Vol. 169. 765 -- 766 . English translation in Soviet Mathematics Doklady 7:4, pp. 999--1000. \u00c8. Ne\u010diporuk.1998. A Boolean function. In Doklady of the Academy of the USSR, Vol. 169. 765--766. English translation in Soviet Mathematics Doklady 7:4, pp. 999--1000.","journal-title":"Doklady of the Academy of the USSR"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344551.1344563"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00219-9"},{"key":"e_1_2_1_12_1","first-page":"183","article-title":"A new lower bound theorem for read-only-once branching programs and its applications. In Proceedings of a DIMACS Workshop on Advances In Computational Complexity Theory","volume":"13","author":"Simon J.","year":"1993","unstructured":"J. Simon and M. Szegedy . 1993 . A new lower bound theorem for read-only-once branching programs and its applications. In Proceedings of a DIMACS Workshop on Advances In Computational Complexity Theory . New Jersey. 13 (1993), 183 -- 193 . J. Simon and M. Szegedy. 1993. A new lower bound theorem for read-only-once branching programs and its applications. In Proceedings of a DIMACS Workshop on Advances In Computational Complexity Theory. New Jersey. 13 (1993), 183--193.","journal-title":"New Jersey."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.46161"},{"key":"e_1_2_1_14_1","unstructured":"D. Wehr. 2012. Exact size of smallest minimum-depth deterministic BPs solving the tree evaluation problem. (2012). Unpublished. http:\/\/www.cs.toronto.edu\/∼wehr\/. D. Wehr. 2012. Exact size of smallest minimum-depth deterministic BPs solving the tree evaluation problem. (2012). Unpublished. http:\/\/www.cs.toronto.edu\/∼wehr\/."},{"key":"e_1_2_1_15_1","volume-title":"Mathematical Foundations of Computer Science","author":"\u017d\u00e1k S.","year":"1984","unstructured":"S. \u017d\u00e1k . 1984. An exponential lower bound for one-time-only branching programs . In Mathematical Foundations of Computer Science 1984 , Michal Chytil and V\u00e1clav Koubek (Eds.). Springer , 562--566 S. \u017d\u00e1k. 1984. An exponential lower bound for one-time-only branching programs. In Mathematical Foundations of Computer Science 1984, Michal Chytil and V\u00e1clav Koubek (Eds.). Springer, 562--566"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3282433","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3282433","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:29Z","timestamp":1750208249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3282433"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,27]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,3,31]]}},"alternative-id":["10.1145\/3282433"],"URL":"https:\/\/doi.org\/10.1145\/3282433","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,27]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}