{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:14:09Z","timestamp":1750306449621,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2015,5,11]],"date-time":"2015-05-11T00:00:00Z","timestamp":1431302400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"PhD Fellowship from Tata Consultancy Services"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2015,5,11]]},"abstract":"<jats:p>\n            We contribute to the program of proving lower bounds on the size of branching programs solving the Tree Evaluation Problem introduced by Cook et al. [2012]. Proving a superpolynomial lower bound for the size of nondeterministic thrifty branching programs would be an important step toward separating NL from P using the tree evaluation problem. First, we show that\n            <jats:italic>Read-Once Nondeterministic Thrifty BPs<\/jats:italic>\n            are equivalent to whole black-white pebbling algorithms, thus showing a tight lower bound (ignoring polynomial factors) for this model. We then introduce a weaker restriction of nondeterministic thrifty branching programs called\n            <jats:italic>Bitwise Independence<\/jats:italic>\n            . The best known [Cook et al. 2012] nondeterministic thrifty branching programs (of size\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>h<\/jats:italic>\n              \/2 + 1\n            <\/jats:sup>\n            )) for the tree evaluation problem are Bitwise Independent. As our main result, we show that any Bitwise Independent Nondeterministic Thrifty Branching Program solving BT\n            <jats:sub>2<\/jats:sub>\n            (h, k) must have at least (k2)\n            <jats:sup>h\/2<\/jats:sup>\n            states. Prior to this work, lower bounds were known for nondeterministic thrifty branching programs only for fixed heights\n            <jats:italic>h<\/jats:italic>\n            = 2, 3, 4 [Cook et al. 2012]. We prove our results by associating a fractional black-white pebbling strategy with any bitwise independent nondeterministic thrifty branching program solving the Tree Evaluation Problem. Such a connection was not known previously, even for fixed heights.\n          <\/jats:p>\n          <jats:p>\n            Our main technique is the entropy method introduced by Jukna and Z\u00e1k [2001] originally in the context of proving lower bounds for read-once branching programs. We also show that the previous lower bounds known [Cook et al. 2012] for deterministic branching programs for the Tree Evaluation Problem can be obtained using this approach. Using this method, we also show tight lower bounds for any\n            <jats:italic>k<\/jats:italic>\n            -way deterministic branching program solving the Tree Evaluation Problem when the instances are restricted to have the same group operation in all internal nodes.\n          <\/jats:p>","DOI":"10.1145\/2751320","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T12:18:00Z","timestamp":1431433080000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Pebbling, Entropy, and Branching Program Size Lower Bounds"],"prefix":"10.1145","volume":"7","author":[{"given":"Balagopal","family":"Komarath","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, India"}]}],"member":"320","published-online":{"date-parts":[[2015,5,11]]},"reference":[{"volume-title":"Computational Complexity\u2014A Modern Approach","author":"Arora Sanjeev","key":"e_1_2_1_1_1","unstructured":"Sanjeev Arora and Boaz Barak . 2009. Computational Complexity\u2014A Modern Approach . Cambridge University Press . I--XXIV, 1--579. Sanjeev Arora and Boaz Barak. 2009. Computational Complexity\u2014A Modern Approach. Cambridge University Press. I--XXIV, 1--579."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90017-V"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2077336.2077337"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795295948"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9049-y"},{"volume-title":"Boolean Function Complexity\u2014Advances and Frontiers","author":"Jukna Stasys","key":"e_1_2_1_7_1","unstructured":"Stasys Jukna . 2012. Boolean Function Complexity\u2014Advances and Frontiers . Springer . Stasys Jukna. 2012. Boolean Function Complexity\u2014Advances and Frontiers. Springer."},{"key":"e_1_2_1_8_1","volume-title":"On uncertainty versus size in branching programs. Electronic Colloquium on Computational Complexity (ECCC) 8, 39","author":"Jukna Stasys","year":"2001","unstructured":"Stasys Jukna and Stanislav Z\u00e1k. 2001. On uncertainty versus size in branching programs. Electronic Colloquium on Computational Complexity (ECCC) 8, 39 ( 2001 ). Stasys Jukna and Stanislav Z\u00e1k. 2001. On uncertainty versus size in branching programs. Electronic Colloquium on Computational Complexity (ECCC) 8, 39 (2001)."},{"volume-title":"FCT, Lecture Notes in Computer Science","author":"Razborov Alexander A.","key":"e_1_2_1_9_1","unstructured":"Alexander A. Razborov . 1991. Lower bounds for deterministic and nondeterministic branching programs . In FCT, Lecture Notes in Computer Science , Vol. 259 , Lothar Budach (Ed.). Springer , 47--60. Alexander A. Razborov. 1991. Lower bounds for deterministic and nondeterministic branching programs. In FCT, Lecture Notes in Computer Science, Vol. 259, Lothar Budach (Ed.). Springer, 47--60."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/322077.322083"},{"key":"e_1_2_1_11_1","volume-title":"Fractional pebbling game lower bounds. ArXiv e-prints (May","author":"Vanderzwet F.","year":"2013","unstructured":"F. Vanderzwet . 2013. Fractional pebbling game lower bounds. ArXiv e-prints (May 2013 ). F. Vanderzwet. 2013. Fractional pebbling game lower bounds. ArXiv e-prints (May 2013)."},{"volume-title":"Introduction to Circuit Complexity\u2014A Uniform Approach","author":"Vollmer Heribert","key":"e_1_2_1_12_1","unstructured":"Heribert Vollmer . 1999. Introduction to Circuit Complexity\u2014A Uniform Approach . Springer . I--XI, 1--270. Heribert Vollmer. 1999. Introduction to Circuit Complexity\u2014A Uniform Approach. Springer. I--XI, 1--270."},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"TAPSOFT","author":"Wegener Ingo","unstructured":"Ingo Wegener . 1987. On the complexity of branching programs and decision trees for clique functions . In TAPSOFT , Vol. 1 , Lecture Notes in Computer Science , Vol. 249, Hartmut Ehrig, Robert A. Kowalski, Giorgio Levi, and Ugo Montanari (Eds.). Springer , 1--12. Ingo Wegener. 1987. On the complexity of branching programs and decision trees for clique functions. In TAPSOFT, Vol. 1, Lecture Notes in Computer Science, Vol. 249, Hartmut Ehrig, Robert A. Kowalski, Giorgio Levi, and Ugo Montanari (Eds.). Springer, 1--12."},{"key":"e_1_2_1_14_1","volume-title":"Lower bound for deterministic semantic-incremental branching programs solving GEN. CoRR abs\/1101.2705","author":"Wehr Dustin","year":"2011","unstructured":"Dustin Wehr . 2011. Lower bound for deterministic semantic-incremental branching programs solving GEN. CoRR abs\/1101.2705 ( 2011 ). Dustin Wehr. 2011. Lower bound for deterministic semantic-incremental branching programs solving GEN. CoRR abs\/1101.2705 (2011)."},{"volume-title":"MFCS, Lecture Notes in Computer Science","author":"Stanislav Z\u00e1k.","key":"e_1_2_1_15_1","unstructured":"Stanislav Z\u00e1k. 1984. An exponential lower bound for one-time-only branching programs . In MFCS, Lecture Notes in Computer Science , Vol. 176 , Michal Chytil and V\u00e1clav Koubek (Eds.). Springer , 562--566. Stanislav Z\u00e1k. 1984. An exponential lower bound for one-time-only branching programs. In MFCS, Lecture Notes in Computer Science, Vol. 176, 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\/2751320","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2751320","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:43:06Z","timestamp":1750225386000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2751320"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,5,11]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,5,11]]}},"alternative-id":["10.1145\/2751320"],"URL":"https:\/\/doi.org\/10.1145\/2751320","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2015,5,11]]},"assertion":[{"value":"2013-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}