{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T00:08:49Z","timestamp":1775779729266,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"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":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>\n            We introduce the\n            <jats:italic>tree evaluation problem<\/jats:italic>\n            , show that it is in\n            <jats:bold>LogDCFL<\/jats:bold>\n            (and hence in\n            <jats:bold>P<\/jats:bold>\n            ), and study its branching program complexity in the hope of eventually proving a superlogarithmic space lower bound. The input to the problem is a rooted, balanced\n            <jats:italic>d<\/jats:italic>\n            -ary tree of height\n            <jats:italic>h<\/jats:italic>\n            , whose internal nodes are labeled with\n            <jats:italic>d<\/jats:italic>\n            -ary functions on [\n            <jats:italic>k<\/jats:italic>\n            ]\u2009=\u2009{1,...,\n            <jats:italic>k<\/jats:italic>\n            }, and whose leaves are labeled with elements of [\n            <jats:italic>k<\/jats:italic>\n            ]. Each node obtains a value in [\n            <jats:italic>k<\/jats:italic>\n            ] equal to its\n            <jats:italic>d<\/jats:italic>\n            -ary function applied to the values of its\n            <jats:italic>d<\/jats:italic>\n            children. The output is the value of the root. We show that the standard black pebbling algorithm applied to the binary tree of height\n            <jats:italic>h<\/jats:italic>\n            yields a deterministic\n            <jats:italic>k<\/jats:italic>\n            -way branching program with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>h<\/jats:sup>\n            ) states solving this problem, and we prove that this upper bound is tight for\n            <jats:italic>h<\/jats:italic>\n            \u2009=\u20092 and\n            <jats:italic>h<\/jats:italic>\n            \u2009=\u20093. We introduce a simple semantic restriction called\n            <jats:italic>thrifty<\/jats:italic>\n            on\n            <jats:italic>k<\/jats:italic>\n            -way branching programs solving tree evaluation problems and show that the same state bound of\n            <jats:italic>\u0398<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>h<\/jats:sup>\n            ) is tight for all\n            <jats:italic>h<\/jats:italic>\n            \u2009\u2265\u20092 for deterministic thrifty programs. We introduce fractional pebbling for trees and show that this yields nondeterministic thrifty programs with\n            <jats:italic>\u0398<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>h\/2+1<\/jats:sup>\n            ) states solving the Boolean problem \u201cdetermine whether the root has value 1\u201d, and prove that this bound is tight for\n            <jats:italic>h<\/jats:italic>\n            \u2009=\u20092,3,4. We also prove that this same bound is tight for unrestricted nondeterministic\n            <jats:italic>k<\/jats:italic>\n            -way branching programs solving the Boolean problem for\n            <jats:italic>h<\/jats:italic>\n            \u2009=\u20092,3.\n          <\/jats:p>","DOI":"10.1145\/2077336.2077337","type":"journal-article","created":{"date-parts":[[2012,2,7]],"date-time":"2012-02-07T15:39:28Z","timestamp":1328629168000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["Pebbles and Branching Programs for Tree Evaluation"],"prefix":"10.1145","volume":"3","author":[{"given":"Stephen","family":"Cook","sequence":"first","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre","family":"McKenzie","sequence":"additional","affiliation":[{"name":"Universit\u00e9 de Montr\u00e9al"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dustin","family":"Wehr","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Braverman","sequence":"additional","affiliation":[{"name":"University of Toronto"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Santhanam","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,1]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"auf der Heide F. M. 1979. A comparison between two variations of a pebble game on graphs. Master\u2019s thesis Fakult\u00e4t f\u00fcr Mathematik Universit\u00e4t Bielefeld. auf der Heide F. M. 1979. A comparison between two variations of a pebble game on graphs. Master\u2019s thesis Fakult\u00e4t f\u00fcr Mathematik Universit\u00e4t Bielefeld."},{"key":"e_1_2_1_2_1","unstructured":"Beame P. and McKenzie P. 2012. A note on Ne\u010diporuk\u2019s method for nondeterministic branching programs. http:\/\/www.cs.washington.edu\/homes\/beame\/papers\/neci.pdf. Beame P. and McKenzie P. 2012. A note on Ne\u010diporuk\u2019s method for nondeterministic branching programs. http:\/\/www.cs.washington.edu\/homes\/beame\/papers\/neci.pdf."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636867"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211022"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200404"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03816-7_16"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909)","author":"Braverman M.","unstructured":"Braverman , M. , Cook , S. , McKenzie , P. , Santhanam , R. , and Wehr , D . 2009b. Fractional pebbling and thrifty branching programs . In Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909) . LIPIcs, 109--120. Braverman, M., Cook, S., McKenzie, P., Santhanam, R., and Wehr, D. 2009b. Fractional pebbling and thrifty branching programs. In Proceedings of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201909). LIPIcs, 109--120."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80048-7"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-001-8195-x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9049-y"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804106"},{"key":"e_1_2_1_13_1","first-page":"119","article-title":"Composition of the universal relation. In Proceedings of the Advances in Computational Complexity Theory","volume":"13","author":"H\u00e5stad J.","year":"1993","unstructured":"H\u00e5stad , J. and Wigderson , A. 1993 . Composition of the universal relation. In Proceedings of the Advances in Computational Complexity Theory , AMS-DIMACS 13. 119 -- 134 . H\u00e5stad, J. and Wigderson, A. 1993. Composition of the universal relation. In Proceedings of the Advances in Computational Complexity Theory, AMS-DIMACS 13. 119--134.","journal-title":"AMS-DIMACS"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206317"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214115"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(80)90136-2"},{"key":"e_1_2_1_17_1","volume-title":"MIT","author":"Loui M.","unstructured":"Loui , M. 1979. The space complexity of two pebble games on trees. Tech. rep. LCS 133 , MIT , Cambridge , Massachussetts . Loui, M. 1979. The space complexity of two pebble games on trees. Tech. rep. LCS 133, MIT, Cambridge, Massachussetts."},{"key":"e_1_2_1_18_1","first-page":"30","article-title":"Polynomial size log depth circuits: between NC 1 and AC 1","volume":"91","author":"Mahajan M.","year":"2007","unstructured":"Mahajan , M. 2007 . Polynomial size log depth circuits: between NC 1 and AC 1 . Bull. EATCS 91 , 30 -- 42 . Mahajan, M. 2007. Polynomial size log depth circuits: between NC 1 and AC 1. Bull. EATCS 91, 30--42.","journal-title":"Bull. EATCS"},{"key":"e_1_2_1_19_1","first-page":"765","article-title":"On a boolean function","volume":"169","author":"Ne\u010diporuk","year":"1966","unstructured":"Ne\u010diporuk , \u00c8. 1966 . On a boolean function . Doklady of the Academy of the USSR 169 , 4, 765 -- 766 . (English translation in Soviet Mathematics Doklady 7, 4, 999--1000.) Ne\u010diporuk, \u00c8. 1966. On a boolean function. Doklady of the Academy of the USSR 169, 4, 765--766. (English translation in Soviet Mathematics Doklady 7, 4, 999--1000.)","journal-title":"Doklady of the Academy of the USSR"},{"key":"e_1_2_1_20_1","unstructured":"Nordstr\u00f6m J. 2009. New wine into old wineskins: A survey of some pebbling classics with supplemental results. http:\/\/people.csail.mit.edu\/jakobn\/research\/. Nordstr\u00f6m J. 2009. New wine into old wineskins: A survey of some pebbling classics with supplemental results. http:\/\/people.csail.mit.edu\/jakobn\/research\/."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1344551.1344563"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/40997.41003"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/647895.740448"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322083"},{"key":"e_1_2_1_25_1","first-page":"5","article-title":"An example of a problem from PTIME and not in NLogSpace. In Proceedings of Tver State University","volume":"6","author":"Taitslin M.","year":"2005","unstructured":"Taitslin , M. 2005 . An example of a problem from PTIME and not in NLogSpace. In Proceedings of Tver State University . Appl. Math. 6 , 12, 5 -- 22 . Taitslin, M. 2005. An example of a problem from PTIME and not in NLogSpace. In Proceedings of Tver State University. Appl. Math. 6, 12, 5--22.","journal-title":"Appl. Math."},{"key":"e_1_2_1_26_1","volume-title":"The Complexity of Boolean Functions","author":"Wegener I.","unstructured":"Wegener , I. 1987. The Complexity of Boolean Functions . Wiley-Teubner Series in Computer Science. B. G. Teubner & John Wiley , Stuttgart. Wegener, I. 1987. The Complexity of Boolean Functions. Wiley-Teubner Series in Computer Science. B. G. Teubner & John Wiley, Stuttgart."},{"key":"e_1_2_1_27_1","series-title":"SIAM Monographs on Discrete Mathematics and Applications","volume-title":"Branching Programs and Binary Decision Diagrams","author":"Wegener I.","unstructured":"Wegener , I. 2000. Branching Programs and Binary Decision Diagrams . SIAM Monographs on Discrete Mathematics and Applications . SIAM , Philadelphia, PA . Wegener, I. 2000. Branching Programs and Binary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications. SIAM, Philadelphia, PA."},{"key":"e_1_2_1_28_1","volume-title":"Department of Computer Science","author":"Wehr D.","unstructured":"Wehr , D. 2010. Pebbling and branching programs solving the tree evaluation problem. MSc research paper , Department of Computer Science , University of Toronto . February. arXiv:1002.4676. Wehr, D. 2010. Pebbling and branching programs solving the tree evaluation problem. MSc research paper, Department of Computer Science, University of Toronto. February. arXiv:1002.4676."},{"key":"e_1_2_1_29_1","unstructured":"Wehr D. 2011. Lower bound for deterministic semantic-incremental branching programs solving GEN. arXiv:1101.2705. Wehr D. 2011. Lower bound for deterministic semantic-incremental branching programs solving GEN. arXiv:1101.2705."},{"key":"e_1_2_1_30_1","unstructured":"Wehr D. 2012. Exact size of the smallest min-depth branching programs solving the tree evaluation problem. http:\/\/www.cs.toronto.edu\/~wehr\/research_docs\/thrifty_and_read-once_exact_size.pdf. Wehr D. 2012. Exact size of the smallest min-depth branching programs solving the tree evaluation problem. http:\/\/www.cs.toronto.edu\/~wehr\/research_docs\/thrifty_and_read-once_exact_size.pdf."}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2077336.2077337","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2077336.2077337","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:46Z","timestamp":1750240486000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2077336.2077337"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2077336.2077337"],"URL":"https:\/\/doi.org\/10.1145\/2077336.2077337","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2010-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}