{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:31:39Z","timestamp":1750221099184,"version":"3.41.0"},"reference-count":22,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T00:00:00Z","timestamp":1549843200000},"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":[[2019,6,30]]},"abstract":"<jats:p>\n            We study projective dimension, a graph parameter, denoted by pd(\n            <jats:italic>G<\/jats:italic>\n            ) for a bipartite graph\n            <jats:italic>G<\/jats:italic>\n            , introduced by Pudl\u00e1k and R\u00f6dl (1992). For a Boolean function\n            <jats:italic>f<\/jats:italic>\n            (on\n            <jats:italic>n<\/jats:italic>\n            bits), Pudl\u00e1k and R\u00f6dl associated a bipartite graph\n            <jats:italic>\n              G\n              <jats:sub>f<\/jats:sub>\n            <\/jats:italic>\n            and showed that size of the optimal branching program computing\n            <jats:italic>f<\/jats:italic>\n            , denoted by bpsize(\n            <jats:italic>f<\/jats:italic>\n            ), is at least pd(\n            <jats:italic>\n              G\n              <jats:sub>f<\/jats:sub>\n            <\/jats:italic>\n            ) (also denoted by pd(\n            <jats:italic>f<\/jats:italic>\n            )). Hence, proving lower bounds for pd(\n            <jats:italic>f<\/jats:italic>\n            ) implies lower bounds for bpsize(\n            <jats:italic>f<\/jats:italic>\n            ). Despite several attempts (Pudl\u00e1k and R\u00f6dl (1992), R\u00f3nyai et al. (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive.\n          <\/jats:p>\n          <jats:p>\n            We observe that there exist a Boolean function\n            <jats:italic>f<\/jats:italic>\n            for which the gap between the pd(\n            <jats:italic>f<\/jats:italic>\n            ) and bpsize(\n            <jats:italic>f<\/jats:italic>\n            )) is 2\n            <jats:sup>\n              \u03a9(\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            . Motivated by the argument in Pudl\u00e1k and R\u00f6dl (1992), we define two variants of projective dimension:\n            <jats:italic>projective dimension with intersection dimension 1<\/jats:italic>\n            , denoted by upd(\n            <jats:italic>f<\/jats:italic>\n            ), and\n            <jats:italic>bitwise decomposable projective dimension<\/jats:italic>\n            , denoted by bitpdim(\n            <jats:italic>f<\/jats:italic>\n            ). We show the following results:\n          <\/jats:p>\n          <jats:p>\n            (a) We observe that there exist a Boolean function\n            <jats:italic>f<\/jats:italic>\n            for which the gap between upd(\n            <jats:italic>f<\/jats:italic>\n            ) and bpsize(\n            <jats:italic>f<\/jats:italic>\n            ) is 2\n            <jats:sup>\n              \u03a9(\n              <jats:italic>n<\/jats:italic>\n              )\n            <\/jats:sup>\n            . In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a constant\n            <jats:italic>c<\/jats:italic>\n            &gt; 0 and for any function\n            <jats:italic>f<\/jats:italic>\n            ,\n          <\/jats:p>\n          <jats:p>\n            bitpdim(\n            <jats:italic>f<\/jats:italic>\n            )\/6 \u2264 bpsize(\n            <jats:italic>f<\/jats:italic>\n            ) \u2264 (bitpdim(\n            <jats:italic>f<\/jats:italic>\n            ))\n            <jats:italic>\n              <jats:sup>c<\/jats:sup>\n            <\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            (b) We introduce a new candidate family of functions\n            <jats:italic>f<\/jats:italic>\n            for showing super-polynomial lower bounds for bitpdim(\n            <jats:italic>f<\/jats:italic>\n            ). As our main result, for this family of functions, we demonstrate gaps between pd(\n            <jats:italic>f<\/jats:italic>\n            ) and the above two new measures for\n            <jats:italic>f<\/jats:italic>\n            :\n          <\/jats:p>\n          <jats:p>\n            pd(\n            <jats:italic>f<\/jats:italic>\n            ) =\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) \u2003 upd(\n            <jats:italic>f<\/jats:italic>\n            ) = \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            ) \u2003 bitpdim(\n            <jats:italic>f<\/jats:italic>\n            ) = \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.5<\/jats:sup>\n            \/ log\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>\n            We adapt Nechiporuk\u2019s techniques for our linear algebraic setting to prove the best-known bpsize lower bounds for bitpdim. Motivated by this linear algebraic setting of our main result, we derive exponential lower bounds for two restricted variants of pd(\n            <jats:italic>f<\/jats:italic>\n            ) and upd(\n            <jats:italic>f<\/jats:italic>\n            ) by observing that they are exactly equal to well-studied graph parameters\u2014bipartite clique cover number and bipartite partition number, respectively.\n          <\/jats:p>","DOI":"10.1145\/3305274","type":"journal-article","created":{"date-parts":[[2019,2,11]],"date-time":"2019-02-11T13:11:45Z","timestamp":1549890705000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Characterization and Lower Bounds for Branching Program Size using Projective Dimension"],"prefix":"10.1145","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1777-7305","authenticated-orcid":false,"given":"Krishnamoorthy","family":"Dinesh","sequence":"first","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sajin","family":"Koroth","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jayalal","family":"Sarma","sequence":"additional","affiliation":[{"name":"Indian Institute of Technology Madras, Chennai, Tamil Nadu, India"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050023"},{"volume-title":"Linear Algebra Methods in Combinatorics with Applications to Geometry and Computer Science","author":"Babai L\u00e1szl\u00f3","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3013516"},{"edition":"2","volume-title":"Random Graphs","author":"Bollob\u00e1s B\u00e9la","key":"e_1_2_1_5_1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(76)90017-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80009-3"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(86)90063-4"},{"volume-title":"Boolean Function Complexity: Advances and Frontiers. Algorithms and Combinatorics","author":"Jukna Stasys","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.926449"},{"volume-title":"Communication Complexity","author":"Kushilevitz Eyal","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000011"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.11.042"},{"volume-title":"Probability and Computing: Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","key":"e_1_2_1_14_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_1_15_1","first-page":"765","article-title":"On a Boolean function","volume":"164","author":"Nechiporuk E. I.","year":"1966","journal-title":"Dokl. Acad. Sci. USSR"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204724"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00115-Y"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02122698"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391289.1391291"},{"edition":"3","volume-title":"Advanced Linear Algebra","author":"Roman Steven","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","first-page":"2001","article-title":"On the number of zero-patterns of a sequence of polynomials","volume":"14","author":"R\u00f3nyai Lajos","year":"2002","journal-title":"J. AMS"},{"volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"Vollmer Heribert","key":"e_1_2_1_22_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3305274","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3305274","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:58:09Z","timestamp":1750208289000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3305274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,11]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,6,30]]}},"alternative-id":["10.1145\/3305274"],"URL":"https:\/\/doi.org\/10.1145\/3305274","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2019,2,11]]},"assertion":[{"value":"2017-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-02-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}