{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:05:27Z","timestamp":1750694727945,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,8,2]],"date-time":"2016-08-02T00:00:00Z","timestamp":1470096000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00037-016-0141-z","type":"journal-article","created":{"date-parts":[[2016,8,2]],"date-time":"2016-08-02T07:18:01Z","timestamp":1470122281000},"page":"835-880","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs"],"prefix":"10.1007","volume":"26","author":[{"given":"Rohit","family":"Gurjar","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arpita","family":"Korwar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Thierauf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,2]]},"reference":[{"key":"141_CR1","doi-asserted-by":"crossref","unstructured":"Leonard M. Adleman & Hendrik W. Lenstra (1986). Finding Irreducible Polynomials over Finite Fields. In Proceedings of the 18th ACM Symposium on Theory of Computing (STOC), 350\u2013355. ACM, New York, NY, USA. ISBN 0-89791-193-8.","DOI":"10.1145\/12130.12166"},{"key":"141_CR2","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal (2005). Proving Lower Bounds Via Pseudo random Generators. In Proceedings of Foundations of 25th Software Technology and Theoretical Computer Science (FSTTCS), volume 3821 of Lecture Notes in Computer Science, 92\u2013105.","DOI":"10.1007\/11590156_6"},{"key":"141_CR3","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal, Rohit Gurjar, Arpita Korwar & Nitin Saxena (2015). Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits. SIAM Journal on Computing 44(3), 669\u2013697. URL http:\/\/dx.doi.org\/10.1137\/140975103 .","DOI":"10.1137\/140975103"},{"key":"141_CR4","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal, Chandan Saha & Nitin Saxena (2013). Quasi-polynomial hitting-set for set-depth-D formulas. In Proceedings of the 45th ACM Symposium on Theory of Computing (STOC), 321\u2013330.","DOI":"10.1145\/2488608.2488649"},{"key":"141_CR5","unstructured":"Jan Behrens & Stephan Waack (1998). Equivalence Test and Or dering Transformation for Parity-OBDDs of Different Variable Order ing. In 15th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 1373, 227\u2013237. Springer-Verlag."},{"key":"141_CR6","doi-asserted-by":"crossref","unstructured":"Michael Ben-Or & Prasoon Tiwari (1988). A Deterministic Algorithm for Sparse Multivariate Polynomial Interpolation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC), 301\u2013309. ACM, New York, NY, USA. ISBN 0-89791-264-0.","DOI":"10.1145\/62212.62241"},{"key":"141_CR7","doi-asserted-by":"crossref","unstructured":"Richard A. Demillo & Richard J. Lipton (1978). A probabilistic remark on algebraic program testing. Information Processing Letters 7(4), 193 \u2013 195. ISSN 0020-0190.","DOI":"10.1016\/0020-0190(78)90067-4"},{"issue":"5","key":"141_CR8","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Dvir Zeev","year":"2007","unstructured":"Zeev Dvir, Amir Shpilka (2007) Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits. SIAM Journal on Computing 36(5): 1404\u20131434","journal-title":"SIAM Journal on Computing"},{"key":"141_CR9","unstructured":"Michael A. Forbes (2014). Polynomial Identity Testing of Read-Once Oblivious Algebraic Branching Programs. Ph.D. thesis, MIT."},{"key":"141_CR10","doi-asserted-by":"crossref","unstructured":"Michael A. Forbes (2015). Deterministic Divisibility Testing via Shifted Partial Derivatives. In Proceedings of the 56th IEEE Symposium on Foundations of Computer Science (FOCS), 451\u2013465. URL http:\/\/dx.doi.org\/10.1109\/FOCS.2015.35 .","DOI":"10.1109\/FOCS.2015.35"},{"key":"141_CR11","doi-asserted-by":"crossref","unstructured":"Michael A. Forbes, Ramprasad Saptharishi & Amir Shpilka (2014). Hitting sets for multilinear read-once algebraic branching programs, in any order. In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC), 867\u2013875.","DOI":"10.1145\/2591796.2591816"},{"key":"141_CR12","doi-asserted-by":"crossref","unstructured":"Michael A. Forbes & Amir Shpilka (2012a). On identity testing of tensors, low-rank recovery and compressed sensing. In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC), 163\u2013172.","DOI":"10.1145\/2213977.2213995"},{"key":"141_CR13","doi-asserted-by":"crossref","unstructured":"Michael A. Forbes & Amir Shpilka (2012b). Quasipolynomial time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. Technical report, CoRR. URL http:\/\/arxiv.org\/abs\/1209.2408 .","DOI":"10.1109\/FOCS.2013.34"},{"key":"141_CR14","unstructured":"Michael A. Forbes & Amir Shpilka (2013). Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS), 243\u2013252. URL http:\/\/arxiv.org\/abs\/1209.2408 ."},{"key":"141_CR15","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF00709139","volume":"8","author":"Gergov Jordan","year":"1996","unstructured":"Jordan Gergov, Christoph Meinel (1996) Mod-2-OBDDs - a Data Structure that Generalizes EXOR-Sum-of-Products and Ordered Binary Decision Diagrams. Formal Methods in System Design 8: 273\u2013282","journal-title":"Formal Methods in System Design"},{"key":"141_CR16","doi-asserted-by":"crossref","unstructured":"Ankit Gupta, Pritish Kamath, Neeraj Kayal & Ramprasad Saptharishi (2013). Arithmetic circuits: A chasm at depth three. In Proceedings of the 54th IEEE Symposium on Foundations of Computer Science (FOCS), 578\u2013587.","DOI":"10.1109\/FOCS.2013.68"},{"key":"141_CR17","unstructured":"Rohit Gurjar, Arpita Korwar, Nitin Saxena & Thomas Thierauf (2015). Deterministic Identity Testing for Sum of Read-once Oblivious Arithmetic Branching Programs. In 30th Conference on Computational Complexity (CCC), 323\u2013346."},{"key":"141_CR18","unstructured":"Maurice J. Jansen, Youming Qiao & Jayalal Sarma (2010). Deterministic Identity Testing of Read-Once Algebraic Branching Programs. Technical report, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"141_CR19","doi-asserted-by":"crossref","unstructured":"Valentine Kabanets & Russell Impagliazzo (2004). Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Computational Complexity 13(1\u20132), 1\u201346. URL http:\/\/dx.doi.org\/10.1007\/s00037-004-0182-6 .","DOI":"10.1007\/s00037-004-0182-6"},{"key":"141_CR20","doi-asserted-by":"crossref","unstructured":"Zohar Shay Karnin & Amir Shpilka (2011). Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Combinatorica 31(3), 333\u2013364.","DOI":"10.1007\/s00493-011-2537-3"},{"key":"141_CR21","unstructured":"Neeraj Kayal, Vineet Nair & Chandan Saha (2015). Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. Technical report, Electronic Colloquium on Computational Complexity (ECCC)."},{"key":"141_CR22","doi-asserted-by":"crossref","unstructured":"Neeraj Kayal & Shubhangi Saraf (2009). Blackbox Polynomial Identity Testing for Depth 3 Circuits. In Proceedings of the 50th IEEE Symposium on Foundations of Computer Science (FOCS), 198\u2013207.","DOI":"10.1109\/FOCS.2009.67"},{"issue":"2","key":"141_CR23","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00037-007-0226-9","volume":"16","author":"Kayal Neeraj","year":"2007","unstructured":"Neeraj Kayal, Nitin Saxena (2007) Polynomial Identity Testing for Depth 3 Circuits. Computational Complexity 16(2): 115\u2013138","journal-title":"Computational Complexity"},{"key":"141_CR24","doi-asserted-by":"crossref","unstructured":"Adam Klivans & Daniel A. Spielman (2001). Randomness efficient identity testing of multivariate polynomials. In Proceedings of the 33rd ACM Symposium on Theory of Computing (STOC), 216\u2013223.","DOI":"10.1145\/380752.380801"},{"key":"141_CR25","unstructured":"Noam Nisan (1991). Lower Bounds for Non-Commutative Computation (Extended Abstract). In Proceedings of the 23rd ACM Symposium on Theory of Computing (STOC), 410\u2013418."},{"key":"141_CR26","unstructured":"Rafael Oliveira, Amir Shpilka & Ben Lee Volk (2015). Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. In 30th Conference on Computational Complexity (CCC), 304\u2013322."},{"issue":"1","key":"141_CR27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"Raz Ran","year":"2005","unstructured":"Ran Raz, Amir Shpilka (2005) Deterministic polynomial identity testing in non-commutative models. Computational Complexity 14(1): 1\u201319","journal-title":"Computational Complexity"},{"issue":"2","key":"141_CR28","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1007\/s00037-009-0270-8","volume":"18","author":"Raz Ran","year":"2009","unstructured":"Ran Raz, Amir Yehudayoff (2009) Lower Bounds and Separa tions for Constant Depth Multilinear Circuits. Computational Complexity 18(2): 171\u2013207","journal-title":"Computational Complexity"},{"key":"141_CR29","doi-asserted-by":"crossref","unstructured":"Petr Savick\u00fd & Ingo Wegener (1997). Efficient algorithms for the transformation between different types of binary decision diagrams. Acta Informatica 34(4), 245\u2013256. ISSN 0001-5903.","DOI":"10.1007\/s002360050083"},{"key":"141_CR30","unstructured":"Nitin Saxena (2009). Progress on Polynomial Identity Testing. In Bulletin of the EATCS, volume 99, 49\u201379."},{"key":"141_CR31","doi-asserted-by":"crossref","unstructured":"Nitin Saxena (2014). Progress on Polynomial Identity Testing-II. In Perspectives in Computational Complexity, 131\u2013146. Birkh\u00e4user Basel.","DOI":"10.1007\/978-3-319-05446-9_7"},{"issue":"1","key":"141_CR32","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1137\/090770679","volume":"40","author":"Saxena Nitin","year":"2011","unstructured":"Nitin Saxena, Comandur Seshadhri (2011) An Almost Opti mal Rank Bound for Depth-3 Identities. SIAM Journal on Computing 40(1): 200\u2013224","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"141_CR33","doi-asserted-by":"crossref","first-page":"1285","DOI":"10.1137\/10848232","volume":"41","author":"Saxena Nitin","year":"2012","unstructured":"Nitin Saxena, Comandur Seshadhri (2012) Blackbox Identity Testing for Bounded Top-Fanin Depth-3 Circuits: The Field Doesn\u2019t Matter. SIAM Journal on Computing 41(5): 1285\u20131298","journal-title":"SIAM Journal on Computing"},{"key":"141_CR34","doi-asserted-by":"crossref","unstructured":"Jacob T. Schwartz (1980). Fast Probabilistic Algorithms for Verifi cation of Polynomial Identities. Journal of the ACM 27(4), 701\u2013717.","DOI":"10.1145\/322217.322225"},{"key":"141_CR35","unstructured":"Amir Shpilka & Amir Yehudayoff (2010). Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science 5(3\u20134), 207\u2013388."},{"key":"141_CR36","doi-asserted-by":"crossref","unstructured":"Richard Zippel (1979). Probabilistic Algorithms for Sparse Polynomials. In Proceedings of the International Symposium on Symbolic and Algebraic Computation (EUROSAM), 216\u2013226. Springer-Verlag. ISBN 3-540-09519-5.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-016-0141-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0141-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0141-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-016-0141-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,11]],"date-time":"2019-09-11T22:04:51Z","timestamp":1568239491000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-016-0141-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,2]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["141"],"URL":"https:\/\/doi.org\/10.1007\/s00037-016-0141-z","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2016,8,2]]}}}