{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T12:59:49Z","timestamp":1753275589246},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,12,15]],"date-time":"2012-12-15T00:00:00Z","timestamp":1355529600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2013,3]]},"DOI":"10.1007\/s00037-012-0054-4","type":"journal-article","created":{"date-parts":[[2012,12,14]],"date-time":"2012-12-14T06:25:46Z","timestamp":1355466346000},"page":"39-69","source":"Crossref","is-referenced-by-count":12,"title":["A Case of Depth-3 Identity Testing, Sparse Factorization and Duality"],"prefix":"10.1007","volume":"22","author":[{"given":"Chandan","family":"Saha","sequence":"first","affiliation":[]},{"given":"Ramprasad","family":"Saptharishi","sequence":"additional","affiliation":[]},{"given":"Nitin","family":"Saxena","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,12,15]]},"reference":[{"key":"54_CR1","unstructured":"Manindra Agrawal (2005). Proving Lower Bounds Via Pseudorandom Generators. In Foundations of Software Technology and Theoretical Computer Science, 92\u2013105."},{"key":"54_CR2","doi-asserted-by":"crossref","unstructured":"Manindra Agrawal & Somenath Biswas (1999). Primality and Identity Testing via Chinese Remaindering. Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, New York City NY 202\u2013209.","DOI":"10.1109\/SFFCS.1999.814592"},{"issue":"2","key":"54_CR3","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","volume":"160","author":"Agrawal Manindra","year":"2004","unstructured":"Manindra Agrawal, Neeraj Kayal, Nitin Saxena (2004) PRIMES is in P. Annals of Mathematics 160(2): 781\u2013793","journal-title":"Annals of Mathematics"},{"key":"54_CR4","unstructured":"Manindra Agrawal & Ramprasad Saptharishi (2009). Classifying polynomials and identity testing. Current Trends in Science, Indian Academy of Sciences 149\u2013162."},{"key":"54_CR5","unstructured":"Manindra Agrawal & V Vinay (2008). Arithmetic circuits: A chasm at depth four. Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, Philadelphia PA 67\u201375."},{"issue":"3","key":"54_CR6","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy (1998) Proof Verification and the Hardness of Approximation Problems. Journal of the ACM 45(3): 501\u2013555","journal-title":"Journal of the ACM"},{"key":"54_CR7","unstructured":"Zhi-Zhong Chen & Ming-Yang Kao (1997). Reducing Randomness via Irrational Numbers. Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing, El Paso TX 200\u2013209."},{"issue":"2","key":"54_CR8","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/0304-3975(91)90157-W","volume":"84","author":"Clausen Michael","year":"1991","unstructured":"Michael Clausen, Andreas W.M. Dress, Johannes Grabmeier, Marek Karpinski (1991) On Zero-Testing and Interpolation of k-Sparse Multivariate Polynomials Over Finite Fields. Theoretical Computer Science 84(2): 151\u2013164","journal-title":"Theoretical Computer Science"},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"Joachim von zur Gathen (1983). Factoring Sparse Multivariate Polynomials. Proceedings of the 24th Annual IEEE Symposium on Foundations of Computer Science, Tucson AZ 172\u2013179.","DOI":"10.1109\/SFCS.1983.15"},{"key":"54_CR10","doi-asserted-by":"crossref","unstructured":"Valentine Kabanets & Russell Impagliazzo (2003). Derandomizing polynomial identity tests means proving circuit lower bounds. Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, San Diego CA 355\u2013364.","DOI":"10.1145\/780542.780595"},{"issue":"2","key":"54_CR11","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":"54_CR12","doi-asserted-by":"crossref","unstructured":"Adam Klivans & Daniel A. Spielman (2001). Randomness efficient identity testing of multivariate polynomials. Proceedings of the Thirty third Annual ACM Symposium on Theory of Computing, Hersonissos, Crete, Greece 216\u2013223.","DOI":"10.1145\/380752.380801"},{"key":"54_CR13","doi-asserted-by":"crossref","unstructured":"Pascal Koiran & Sylvain Perifel (2007). The complexity of two problems on arithmetic circuits. Theoretical Computer Science 389(1-2), 172\u2013181.","DOI":"10.1016\/j.tcs.2007.08.008"},{"key":"54_CR14","doi-asserted-by":"crossref","unstructured":"Daniel Lewin & Salil P. Vadhan (1998). Checking Polynomial Identities over any Field: Towards a Derandomization? Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, Dallas TX 438\u2013447.","DOI":"10.1145\/276698.276856"},{"key":"54_CR15","unstructured":"L\u00e1szl\u00f3 Lova\u015bz (1979). On determinants, matchings, and random algorithms. In Fundamentals of Computation Theory, 565\u2013574."},{"key":"54_CR16","doi-asserted-by":"crossref","unstructured":"Carsten Lund, Lance Fortnow, Howard J. Karloff & Noam Nisan (1990). Algebraic Methods for Interactive Proof Systems. Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis MO 2\u201310.","DOI":"10.1109\/FSCS.1990.89518"},{"key":"54_CR17","doi-asserted-by":"crossref","unstructured":"Ran Raz (2010). Tensor-rank and lower bounds for arithmetic formulas. In Proceedings of the Fourty-second Annual ACM Symposium on Theory of Computing, Cambridge, MA, USA, 659\u2013666.","DOI":"10.1145\/1806689.1806780"},{"key":"54_CR18","unstructured":"Ran Raz & Amir Shpilka (2004). Deterministic Polynomial Identity Testing in Non-Commutative Models. Proceedings of the 19th IEEE Conference on Computational Complexity, Amherst MA 215\u2013222."},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Shubhangi Saraf & Ilya Volkovich (2011). Black-box identity testing of depth-4 multilinear circuits. Proceedings of the Fourty-third Annual ACM Symposium on Theory of Computing, San Jose CA.","DOI":"10.1145\/1993636.1993693"},{"key":"54_CR20","doi-asserted-by":"crossref","unstructured":"Nitin Saxena (2008). Diagonal Circuit Identity Testing and Lower Bounds. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming ICALP, Reykjavik Iceland, 927 60\u201371.","DOI":"10.1007\/978-3-540-70575-8_6"},{"key":"54_CR21","unstructured":"Nitin Saxena: Progress on Polynomial Identity Testing. Bulletin of the European Association for Theoretical Computer Science 90, 49\u201379 (2009)"},{"key":"54_CR22","doi-asserted-by":"crossref","unstructured":"Nitin Saxena & C. Seshadhri (2011). Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn\u2019t matter. Proceedings of the Fourty-third Annual ACM Symposium on Theory of Computing, San Jose CA.","DOI":"10.1145\/1993636.1993694"},{"issue":"4","key":"54_CR23","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"Schwartz Jacob T.","year":"1980","unstructured":"Jacob T. Schwartz (1980) Fast Probabilistic Algorithms for Verification of Polynomial Identities. Journal of the ACM 27(4): 701\u2013717","journal-title":"Journal of the ACM"},{"key":"54_CR24","unstructured":"Adi Shamir (1990). IP=PSPACE. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis MO, 939 11\u201315."},{"issue":"3-4","key":"54_CR25","first-page":"207","volume":"5","author":"Shpilka Amir","year":"2010","unstructured":"Amir Shpilka, Amir Yehudayoff (2010) Arithmetic Circuits: A survey of recent results and open questions. Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science 5(3-4): 207\u2013388","journal-title":"Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science"},{"key":"54_CR26","doi-asserted-by":"crossref","unstructured":"Richard Zippel (1979). Probabilistic algorithms for sparse polynomials. EUROSAM 216\u2013226.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0054-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00037-012-0054-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-012-0054-4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,3]],"date-time":"2022-02-03T11:16:49Z","timestamp":1643887009000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00037-012-0054-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,15]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,3]]}},"alternative-id":["54"],"URL":"https:\/\/doi.org\/10.1007\/s00037-012-0054-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,15]]}}}