{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T11:27:35Z","timestamp":1649071655902},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100007296","name":"Infosys Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100007296","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00224-021-10053-w","type":"journal-article","created":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T12:07:58Z","timestamp":1626350878000},"page":"56-88","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Univariate Ideal Membership Parameterized by Rank, Degree, and Number of Generators"],"prefix":"10.1007","volume":"66","author":[{"given":"V.","family":"Arvind","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Abhranil","family":"Chatterjee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rajit","family":"Datta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Partha","family":"Mukhopadhyay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"issue":"1\u20132","key":"10053_CR1","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1017\/S0963548398003411","volume":"8","author":"N Alon","year":"1999","unstructured":"Alon, N.: Combinatorial nullstellensatz. Comb. Probab. Comput. 8(1\u20132), 7\u201329 (1999). http:\/\/dl.acm.org\/citation.cfm?id=971651.971653","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"10053_CR2","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1006\/jctb.1997.1753","volume":"70","author":"N Alon","year":"1997","unstructured":"Alon, N., Tarsi, M.: A note on graph colorings and graph polynomials. J. Comb. Theory Ser. B. 70(1), 197\u2013201 (1997). https:\/\/doi.org\/10.1006\/jctb.1997.1753","journal-title":"J. Comb. Theory Ser. B."},{"issue":"4","key":"10053_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42 (4), 844\u2013856 (1995). https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"J. ACM"},{"issue":"2","key":"10053_CR4","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1002\/(SICI)1097-0118(199610)23:2<185::AID-JGT9>3.0.CO;2-P","volume":"23","author":"A Kotlov","year":"1996","unstructured":"Kotlov, A., Lov\u00e1sz, L: The rank and size of graphs. J. Graph Theory 23(2), 185\u2013189 (1996)","journal-title":"J. Graph Theory"},{"key":"10053_CR5","unstructured":"Arvind, V., Chatterjee, A., Datta, R., Mukhopadhyay, P.: Fast exact algorithms using Hadamard product of polynomials. arXiv:1807.04496 (2018)"},{"key":"10053_CR6","doi-asserted-by":"publisher","unstructured":"Arvind, V., Chatterjee, A., Datta, R., Mukhopadhyay, P.: Univariate ideal membership parameterized by rank degree, and number of generators. In: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, pp 7:1\u20137:18 (2018). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2018.7","DOI":"10.4230\/LIPIcs.FSTTCS.2018.7"},{"key":"10053_CR7","unstructured":"Arvind, V., Chatterjee, A., Datta, R., Mukhopadhyay, P.: Efficient black-box identity testing over free group algebra (accepted in RANDOM 2019). arXiv:1904.12337 (2019)"},{"issue":"4","key":"10053_CR8","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1016\/j.ic.2009.06.003","volume":"208","author":"V Arvind","year":"2010","unstructured":"Arvind, V., Mukhopadhyay, P.: The ideal membership problem and polynomial identity testing. Inf. Comput. 208(4), 351\u2013363 (2010). https:\/\/doi.org\/10.1016\/j.ic.2009.06.003","journal-title":"Inf. Comput."},{"issue":"1","key":"10053_CR9","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1287\/moor.21.1.65","volume":"21","author":"AI Barvinok","year":"1996","unstructured":"Barvinok, A.I.: Two algorithmic results for the traveling salesman problem. Math. Oper. Res. 21(1), 65\u201384 (1996). https:\/\/doi.org\/10.1287\/moor.21.1.65","journal-title":"Math. Oper. Res."},{"issue":"2","key":"10053_CR10","doi-asserted-by":"publisher","first-page":"947","DOI":"10.1007\/s00453-015-9981-1","volume":"74","author":"A Bj\u00f6rklund","year":"2016","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, L.: Constrained multilinear detection and generalized graph motifs. Algorithmica 74(2), 947\u2013967 (2016). https:\/\/doi.org\/10.1007\/s00453-015-9981-1","journal-title":"Algorithmica"},{"key":"10053_CR11","doi-asserted-by":"publisher","unstructured":"Brand, C., Dell, H., Husfeldt, T.: Extensor-coding. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA June 25-29, 2018. https:\/\/doi.org\/10.1145\/3188745.3188902, pp 151\u2013164 (2018)","DOI":"10.1145\/3188745.3188902"},{"key":"10053_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-35651-8","volume-title":"Ideals Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3\/e (Undergraduate Texts in Mathematics)","author":"DA Cox","year":"2007","unstructured":"Cox, D.A., Little, J., O\u2019Shea, D.: Ideals Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3\/e (Undergraduate Texts in Mathematics). Springer-Verlag, New York, Inc., Secaucus, NJ USA (2007)"},{"key":"10053_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized Algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan, M., Fomin, FV., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, New York (2015). https:\/\/doi.org\/10.1007\/978-3-319-21275-3"},{"issue":"4","key":"10053_CR14","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"RA Demillo","year":"1978","unstructured":"Demillo, RA., Lipton, RJ.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7(4), 193\u2013195 (1978). http:\/\/www.sciencedirect.com\/science\/article\/pii\/0020019078900674, https:\/\/doi.org\/10.1016\/0020-0190(78)90067-4","journal-title":"Inf. Process. Lett."},{"key":"10053_CR15","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/S1571-0661(04)81014-4","volume":"78","author":"RG Downey","year":"2003","unstructured":"Downey, RG., Estivill-Castro, V., Fellows, M.R., Prieto-Rodriguez, E., Rosamond, FA.: Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electr. Notes Theor. Comput. Sci. 78, 209\u2013222 (2003). https:\/\/doi.org\/10.1016\/S1571-0661(04)81014-4","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"10053_CR16","doi-asserted-by":"publisher","unstructured":"Forbes, M., Shpilka, A.: Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In: 16th Annual Symposium on Foundations of Computer Science, 09 2012. https:\/\/doi.org\/10.1109\/FOCS.2013.34 (1975)","DOI":"10.1109\/FOCS.2013.34"},{"key":"10053_CR17","first-page":"73","volume":"17","author":"N Kayal","year":"2010","unstructured":"Kayal, N.: Algorithms for arithmetic circuits. Electron. Colloq. Comput. Complex. (ECCC) 17, 73 (2010)","journal-title":"Electron. Colloq. Comput. Complex. (ECCC)"},{"issue":"2","key":"10053_CR18","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s00037-007-0226-9","volume":"16","author":"N Kayal","year":"2007","unstructured":"Kayal, N., Saxena, N.: Polynomial identity testing for depth 3 circuits. Comput. Complex. 16(2), 115\u2013138 (2007). https:\/\/doi.org\/10.1007\/s00037-007-0226-9","journal-title":"Comput. Complex."},{"issue":"4","key":"10053_CR19","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1006\/jcom.1996.0019","volume":"12","author":"P Koiran","year":"1996","unstructured":"Koiran, P.: Hilbert\u2019s nullstellensatz is in the polynomial hierarchy. J. Complex. 12(4), 273\u2013286 (1996). https:\/\/doi.org\/10.1006\/jcom.1996.0019","journal-title":"J. Complex."},{"issue":"1","key":"10053_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1097-0118(199709)26:1<1::AID-JGT1>3.0.CO;2-N","volume":"26","author":"A Kotlov","year":"1997","unstructured":"Kotlov, A.: Rank and chromatic number of a graph. J. Graph Theory 26(1), 1\u20138 (1997)","journal-title":"J. Graph Theory"},{"key":"10053_CR21","doi-asserted-by":"publisher","unstructured":"Koutis, I.: Faster algebraic algorithms for path and packing problems. In: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, pp 575\u2013586 (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_47","DOI":"10.1007\/978-3-540-70575-8_47"},{"issue":"22","key":"10053_CR22","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1016\/j.ipl.2012.08.008","volume":"112","author":"I Koutis","year":"2012","unstructured":"Koutis, I.: Constrained multilinear detection for faster functional motif discovery. Inf. Process. Lett. 112(22), 889\u2013892 (2012). https:\/\/doi.org\/10.1016\/j.ipl.2012.08.008","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"10053_CR23","doi-asserted-by":"publisher","first-page":"31:1","DOI":"10.1145\/2885499","volume":"12","author":"I Koutis","year":"2016","unstructured":"Koutis, I., Williams, R.: LIMITS and applications of group algebras for parameterized problems. ACM Trans. Algorithm. 12(3), 31:1\u201331:18 (2016). https:\/\/doi.org\/10.1145\/2885499","journal-title":"ACM Trans. Algorithm."},{"key":"10053_CR24","doi-asserted-by":"crossref","unstructured":"Lee, H.: Power sum decompositions of elementary symmetric polynomials. Linear Algebra Appl. 492(08) (2015)","DOI":"10.1016\/j.laa.2015.11.018"},{"issue":"3","key":"10053_CR25","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1307\/mmj\/1028999140","volume":"09","author":"K Mahler","year":"1964","unstructured":"Mahler, K.: An inequality for the discriminant of a polynomial. Mich. Math. J. 09(3), 257\u2013262 (1964). https:\/\/doi.org\/10.1307\/mmj\/1028999140","journal-title":"Mich. Math. J."},{"key":"10053_CR26","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E Mayr","year":"1982","unstructured":"Mayr, E., Meyer, A.: The complexity of word problem for commutative semigroups and polynomial ideals. Adv. Math 46, 305\u2013329 (1982)","journal-title":"Adv. Math"},{"key":"10053_CR27","unstructured":"Pratt, K.: Faster algorithms via waring decompositions. arXiv:1807.06194 (2018)"},{"key":"10053_CR28","doi-asserted-by":"publisher","unstructured":"Saxena, N.: Diagonal circuit identity testing and lower bounds. In: Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, pp 60\u201371 (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_6","DOI":"10.1007\/978-3-540-70575-8_6"},{"issue":"5","key":"10053_CR29","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/2528403","volume":"60","author":"N Saxena","year":"2013","unstructured":"Saxena, N., Seshadhri, C.: From sylvester-gallai configurations to rank bounds: Improved blackbox identity test for depth-3 circuits. J. ACM 60(5), 33:1\u201333:33 (2013). https:\/\/doi.org\/10.1145\/2528403","journal-title":"J. ACM"},{"key":"10053_CR30","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, STOC \u201978, pp 216\u2013226. ACM, New York, NY USA (1978)","DOI":"10.1145\/800133.804350"},{"issue":"4","key":"10053_CR31","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithm for verification of polynomial identities. J. ACM. 27(4), 701\u2013717 (1980)","journal-title":"J. ACM."},{"key":"10053_CR32","unstructured":"Sudan, M.: Lectures on algebra and computation. Lecture notes 6,12,13,14 (1998)"},{"issue":"6","key":"10053_CR33","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/j.ipl.2008.11.004","volume":"109","author":"R Williams","year":"2009","unstructured":"Williams, R.: Finding paths of length k in O\u2217(2k) time. Inf. Process. Lett. 109(6), 315\u2013318 (2009). https:\/\/doi.org\/10.1016\/j.ipl.2008.11.004","journal-title":"Inf. Process. Lett."},{"key":"10053_CR34","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Proc. of the Int. Sym. on Symbolic and Algebraic Computation, pp 216\u2013226 (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10053-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10053-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10053-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,28]],"date-time":"2022-01-28T04:37:03Z","timestamp":1643344623000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10053-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["10053"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10053-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"28 June 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 July 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}