{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:58:24Z","timestamp":1760061504440},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_35","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T16:10:36Z","timestamp":1402503036000},"page":"417-428","source":"Crossref","is-referenced-by-count":10,"title":["Testing Equivalence of Polynomials under Shifts"],"prefix":"10.1007","author":[{"given":"Zeev","family":"Dvir","sequence":"first","affiliation":[]},{"given":"Rafael Mendes","family":"de Oliveira","sequence":"additional","affiliation":[]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Saha, C., Saxena, N.: Quasi-polynomial hitting-set for set-depth-d formulas. In: STOC, pp. 321\u2013330 (2013)","DOI":"10.1145\/2488608.2488649"},{"issue":"3","key":"35_CR2","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(83)90110-X","volume":"22","author":"W. Baur","year":"1983","unstructured":"Baur, W., Strassen, V.: The complexity of partial derivatives. Theoretical Computer Science\u00a022(3), 317\u2013330 (1983)","journal-title":"Theoretical Computer Science"},{"key":"35_CR3","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/978-3-540-33275-6_15","volume-title":"Algebraic geometry and geometric modeling","author":"E. Carlini","year":"2006","unstructured":"Carlini, E.: Reducing the number of variables of a polynomial. In: Algebraic geometry and geometric modeling, pp. 237\u2013247. Springer, Heidelberg (2006)"},{"issue":"4","key":"35_CR4","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"R.A. DeMillo","year":"1978","unstructured":"DeMillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett.\u00a07(4), 193\u2013195 (1978)","journal-title":"Inf. Process. Lett."},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"Forbes, M.A., Shpilka, A.: On identity testing of tensors, low-rank recovery and compressed sensing. In: Proceedings of the 44th Annual STOC, pp. 163\u2013172 (2012)","DOI":"10.1145\/2213977.2213995"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"Forbes, M.A., Shpilka, A.: Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In: Proceedings of the 54th Annual FOCS (2013)","DOI":"10.1109\/FOCS.2013.34"},{"key":"35_CR7","first-page":"132","volume":"20","author":"M.A. Forbes","year":"2013","unstructured":"Forbes, M.A., Saptharishi, R., Shpilka, A.: Pseudorandomness for multilinear read-once algebraic branching programs, in any order. Electronic Colloquium on Computational Complexity (ECCC)\u00a020, 132 (2013)","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"35_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-56686-4_41","volume-title":"Applied Algebra, Algebraic Algorithms and Error-Correcting Codes","author":"D. Grigoriev","year":"1993","unstructured":"Grigoriev, D., Karpinski, M.: A zero-test and an interpolation algorithm for the shifted sparse polynomials. In: Moreno, O., Cohen, G., Mora, T. (eds.) AAECC 1993. LNCS, vol.\u00a0673, pp. 162\u2013169. Springer, Heidelberg (1993)"},{"key":"35_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1145\/220346.220359","volume-title":"Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, ISSAC 1995","author":"D. Grigoriev","year":"1995","unstructured":"Grigoriev, D., Lakshman, Y.N.: Algorithms for computing sparse shifts for multivariate polynomials. In: Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation, ISSAC 1995, pp. 96\u2013103. ACM, New York (1995)"},{"issue":"1-2","key":"35_CR10","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1016\/S0304-3975(96)00188-0","volume":"180","author":"D. Grigoriev","year":"1997","unstructured":"Grigoriev, D.: Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines. Theoretical Computer Science\u00a0180(1-2), 217\u2013228 (1997)","journal-title":"Theoretical Computer Science"},{"key":"35_CR11","first-page":"643","volume-title":"Proceedings of the 44th symposium on Theory of Computing, STOC 2012","author":"N. Kayal","year":"2012","unstructured":"Kayal, N.: Affine projections of polynomials: extended abstract. In: Proceedings of the 44th symposium on Theory of Computing, STOC 2012, pp. 643\u2013662. ACM, New York (2012)"},{"key":"35_CR12","doi-asserted-by":"crossref","unstructured":"Klivans, A., Spielman, D.: Randomness efficient identity testing of multivariate polynomials. In: Proceedings of the 33rd Annual STOC, pp. 216\u2013223 (2001)","DOI":"10.1145\/380752.380801"},{"key":"35_CR13","doi-asserted-by":"crossref","unstructured":"Karnin, Z.S., Shpilka, A.: Reconstruction of generalized depth-3 arithmetic circuits with bounded top fan-in. In: Proceedings of the 24th Annual CCC, pp. 274\u2013285 (2009)","DOI":"10.1109\/CCC.2009.18"},{"key":"35_CR14","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1145\/190347.190373","volume-title":"Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1994","author":"Y.N. Lakshman","year":"1994","unstructured":"Lakshman, Y.N., Saunders, B.D.: On computing sparse shifts for univariate polynomials. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation, ISSAC 1994, pp. 108\u2013113. ACM, New York (1994)"},{"issue":"4","key":"35_CR15","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM\u00a027(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"issue":"6","key":"35_CR16","doi-asserted-by":"publisher","first-page":"2130","DOI":"10.1137\/070694879","volume":"38","author":"A. Shpilka","year":"2009","unstructured":"Shpilka, A.: Interpolation of depth-3 arithmetic circuits with two multiplication gates. SIAM J. on Computing\u00a038(6), 2130\u20132161 (2009)","journal-title":"SIAM J. on Computing"},{"key":"35_CR17","doi-asserted-by":"crossref","unstructured":"Saha, C., Saptharishi, R., Saxena, N.: A case of depth-3 identity testing, sparse factorization and duality. Computational Complexity, 1\u201331 (2013)","DOI":"10.1007\/s00037-012-0054-4"},{"key":"35_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R. Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, K.W. (ed.) EUROSAM 1979 and ISSAC 1979. LNCS, vol.\u00a072, pp. 216\u2013226. Springer, Heidelberg (1979)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T06:06:09Z","timestamp":1689314769000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}