{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:07Z","timestamp":1759638607613,"version":"3.41.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T00:00:00Z","timestamp":1515542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Community\u2019s Seventh Framework Programme","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}]},{"name":"Princeton Center for Theoretical Computer Science","award":["257575"],"award-info":[{"award-number":["257575"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2018,3,31]]},"abstract":"<jats:p>\n            Read-\n            <jats:italic>k<\/jats:italic>\n            oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ABP). In this work, we give an exponential lower bound of exp (\n            <jats:italic>n\/k<\/jats:italic>\n            <jats:sup>\n              <jats:italic>O<\/jats:italic>\n              (\n              <jats:italic>k<\/jats:italic>\n              )\n            <\/jats:sup>\n            ) on the width of any read-\n            <jats:italic>k<\/jats:italic>\n            oblivious ABP computing some explicit multilinear polynomial\n            <jats:italic>f<\/jats:italic>\n            that is computed by a polynomial-size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2\n            <jats:sup>\n              \u00d5(\n              <jats:italic>n<\/jats:italic>\n              <jats:sup>1\u22121\/2<\/jats:sup>\n              <jats:sup>\n                <jats:italic>k<\/jats:italic>\n                \u22121\n              <\/jats:sup>\n              )\n            <\/jats:sup>\n            and needs white box access only to know the order in which the variables appear in the ABP.\n          <\/jats:p>","DOI":"10.1145\/3170709","type":"journal-article","created":{"date-parts":[[2018,1,10]],"date-time":"2018-01-10T16:51:38Z","timestamp":1515603098000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Identity Testing and Lower Bounds for Read-\n            <i>k<\/i>\n            Oblivious Algebraic Branching Programs"],"prefix":"10.1145","volume":"10","author":[{"given":"Matthew","family":"Anderson","sequence":"first","affiliation":[{"name":"Union College, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Forbes","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ramprasad","family":"Saptharishi","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research (TIFR), Mumbai, India"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben Lee","family":"Volk","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,1,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11590156_6"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/140975103"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.32"},{"key":"e_1_2_1_4_1","volume-title":"Ziegler","author":"Aigner Martin","year":"2004","unstructured":"Martin Aigner and G\u00fcnter M . Ziegler . 2004 . Proofs from THE BOOK. Springer . Martin Aigner and G\u00fcnter M. Ziegler. 2004. Proofs from THE BOOK. Springer."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(85)80028-7"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the of the 31st Annual Computational Complexity Conference (CCC","volume":"50","author":"Anderson Matthew","year":"2016","unstructured":"Matthew Anderson , Michael A. Forbes , Ramprasad Saptharishi , Amir Shpilka , and Ben Lee Volk . 2016 . Identity testing and lower bounds for read-k oblivious algebraic branching programs . In Proceedings of the of the 31st Annual Computational Complexity Conference (CCC 2016), Vol. 50 . 30:1--30:25. Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, and Ben Lee Volk. 2016. Identity testing and lower bounds for read-k oblivious algebraic branching programs. In Proceedings of the of the 31st Annual Computational Complexity Conference (CCC 2016), Vol. 50. 30:1--30:25."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0097-4"},{"key":"e_1_2_1_9_1","unstructured":"Vikraman Arvind and S. Raja. 2016. Some lower bound results for set-multilinear arithmetic computations. Chicago J. Theoret. Comput. Sci. Retrieved from http:\/\/cjtcs.cs.uchicago.edu\/articles\/2016\/6\/contents.html.  Vikraman Arvind and S. Raja. 2016. Some lower bound results for set-multilinear arithmetic computations. Chicago J. Theoret. Comput. Sci. Retrieved from http:\/\/cjtcs.cs.uchicago.edu\/articles\/2016\/6\/contents.html."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/32928.32930"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/636865.636867"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2013.v009a007"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.57"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200404"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/120875673"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2011.23"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/05063605X"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1957995.1957999"},{"key":"e_1_2_1_20_1","first-page":"463","article-title":"A combinatorial problem in geometry","volume":"2","author":"Erd\u0151s Paul","year":"1935","unstructured":"Paul Erd\u0151s and George Szekeres . 1935 . A combinatorial problem in geometry . Compositio Math. 2 (1935), 463 -- 470 . Paul Erd\u0151s and George Szekeres. 1935. A combinatorial problem in geometry. Compositio Math. 2 (1935), 463--470.","journal-title":"Compositio Math."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591816"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM 2013)","volume":"8096","author":"Michael","unstructured":"Michael A. Forbes and Amir Shpilka. 2013. Explicit noether normalization for simultaneous conjugation via polynomial identity testing . In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM 2013) (Lecture Notes in Computer Science) , Vol. 8096 . Springer, 527--542. Michael A. Forbes and Amir Shpilka. 2013. Explicit noether normalization for simultaneous conjugation via polynomial identity testing. In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM 2013) (Lecture Notes in Computer Science), Vol. 8096. Springer, 527--542."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.34"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591824"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.77"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.68"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629541"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-016-0141-z"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800141.804674"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.78"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195190"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 30th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS","volume":"8","author":"Jansen Maurice J.","year":"2010","unstructured":"Maurice J. Jansen , Youming Qiao , and Jayalal Sarma . 2010 . Deterministic black-box identity testing $pi$-ordered algebraic branching programs . In Proceedings of the 30th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), Vol. 8 . 296--307. Maurice J. Jansen, Youming Qiao, and Jayalal Sarma. 2010. Deterministic black-box identity testing $pi$-ordered algebraic branching programs. In Proceedings of the 30th International Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), Vol. 8. 296--307."},{"key":"e_1_2_1_34_1","volume-title":"Electron. Colloq. Comput. Complex. (ECCC) 17","author":"Jansen Maurice J.","year":"2010","unstructured":"Maurice J. Jansen , Youming Qiao , and Jayalal Sarma . 2010 . Deterministic identity testing of read-once algebraic branching programs . Electron. Colloq. Comput. Complex. (ECCC) 17 (2010), 84. Maurice J. Jansen, Youming Qiao, and Jayalal Sarma. 2010. Deterministic identity testing of read-once algebraic branching programs. Electron. Colloq. Comput. Complex. (ECCC) 17 (2010), 84."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-004-0182-6"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/110824516"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.15"},{"key":"e_1_2_1_39_1","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)","volume":"47","author":"Kayal Neeraj","year":"2016","unstructured":"Neeraj Kayal , Vineet Nair , and Chandan Saha . 2016 . Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits . In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (LIPIcs), Vol. 47 . 46:1--46:15. Neeraj Kayal, Vineet Nair, and Chandan Saha. 2016. Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) (LIPIcs), Vol. 47. 46:1--46:15."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591847"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.67"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-007-0226-9"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.041"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0102-y"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993672"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1953-0053256-2"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591827"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.46"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135627"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.15"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103462"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_2_1_55_1","first-page":"61","article-title":"Lower bounds on the complexity of realization of characteristic functions of binary codes by branching programs","volume":"51","author":"Okolnishnikova E. A.","year":"1991","unstructured":"E. A. Okolnishnikova . 1991 . Lower bounds on the complexity of realization of characteristic functions of binary codes by branching programs . Metody Diskretnogo Analiza 51 (1991), 61 -- 83 . E. A. Okolnishnikova. 1991. Lower bounds on the complexity of realization of characteristic functions of binary codes by branching programs. Metody Diskretnogo Analiza 51 (1991), 61--83.","journal-title":"Metody Diskretnogo Analiza"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/2833227.2833242"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0188-8"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0270-8"},{"key":"e_1_2_1_59_1","volume-title":"Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM","author":"Reingold Omer","year":"2013","unstructured":"Omer Reingold , Thomas Steinke , and Salil P. Vadhan . 2013. Pseudorandomness for regular branching programs via fourier analysis . In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM 2013 ). 655--670. Omer Reingold, Thomas Steinke, and Salil P. Vadhan. 2013. Pseudorandomness for regular branching programs via fourier analysis. In Proceedings of the 17th International Workshop on Randomization and Computation (RANDOM 2013). 655--670."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993693"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/10848232"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/1880918.1880964"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0105-8"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000039"},{"key":"e_1_2_1_66_1","volume-title":"Electron. Colloq. Comput. Complex. (ECCC) 19","author":"Steinke Thomas","year":"2012","unstructured":"Thomas Steinke . 2012 . Pseudorandomness for permutation branching programs without the group theory . Electron. Colloq. Comput. Complex. (ECCC) 19 (2012), 83. Thomas Steinke. 2012. Pseudorandomness for permutation branching programs without the group theory. Electron. Colloq. Comput. Complex. (ECCC) 19 (2012), 83."},{"key":"e_1_2_1_67_1","volume-title":"Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM","author":"Steinke Thomas","year":"2014","unstructured":"Thomas Steinke , Salil P. Vadhan , and Andrew Wan . 2014 . Pseudorandomness and fourier growth bounds for width-3 branching programs . In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM 2014). 885--899. Thomas Steinke, Salil P. Vadhan, and Andrew Wan. 2014. Pseudorandomness and fourier growth bounds for width-3 branching programs. In Proceedings of the 18th International Workshop on Randomization and Computation (RANDOM 2014). 885--899."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.09.004"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276881"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212043"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.46161"},{"key":"e_1_2_1_72_1","volume-title":"Proceedings of the 9th International Symposium on the Mathematical Foundations of Computer Science (MFCS 1984)","volume":"176","author":"Z\u00e1k Stanislav","year":"1984","unstructured":"Stanislav Z\u00e1k . 1984 . An exponential lower bound for one-time-only branching programs . In Proceedings of the 9th International Symposium on the Mathematical Foundations of Computer Science (MFCS 1984) (Lecture Notes in Computer Science) , Vol. 176 . Springer, 562--566. Stanislav Z\u00e1k. 1984. An exponential lower bound for one-time-only branching programs. In Proceedings of the 9th International Symposium on the Mathematical Foundations of Computer Science (MFCS 1984) (Lecture Notes in Computer Science), Vol. 176. Springer, 562--566."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.5555\/646670.698972"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170709","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3170709","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:26:58Z","timestamp":1750213618000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3170709"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1,10]]},"references-count":72,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,3,31]]}},"alternative-id":["10.1145\/3170709"],"URL":"https:\/\/doi.org\/10.1145\/3170709","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2018,1,10]]},"assertion":[{"value":"2016-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-01-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}