{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,24]],"date-time":"2026-02-24T05:34:25Z","timestamp":1771911265013,"version":"3.50.1"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,10]],"date-time":"2022-01-10T00:00:00Z","timestamp":1641772800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,10]],"date-time":"2022-01-10T00:00:00Z","timestamp":1641772800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s00453-021-00900-0","type":"journal-article","created":{"date-parts":[[2022,1,10]],"date-time":"2022-01-10T00:03:16Z","timestamp":1641772996000},"page":"436-463","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast Exact Algorithms Using Hadamard Product of Polynomials"],"prefix":"10.1007","volume":"84","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1988-7866","authenticated-orcid":false,"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":[[2022,1,10]]},"reference":[{"issue":"4","key":"900_CR1","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"},{"key":"900_CR2","unstructured":"Arvind, V., Chatterjee, A., Datta, R., Mukhopadhyay, P.: Fast exact algorithms using Hadamard product of polynomials. CoRR arXiv:1807.04496 (2018)"},{"key":"900_CR3","unstructured":"Arvind, V., Chatterjee, A., Datta, R., Mukhopadhyay, P.: Efficient black-box identity testing over free group algebra (accepted in RANDOM 2019). CoRR arXiv:1904.12337 (2019)"},{"key":"900_CR4","unstructured":"Arvind, V., Joglekar, P.S., Srinivasan, S.: Arithmetic circuits and the Hadamard product of polynomials. In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009, December 15\u201317, 2009, IIT Kanpur, India, pp. 25\u201336 (2009)"},{"key":"900_CR5","doi-asserted-by":"publisher","unstructured":"Arvind, V., Srinivasan, S.: On the hardness of the noncommutative determinant. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, pp. 677\u2013686 (2010). https:\/\/doi.org\/10.1145\/1806689.1806782","DOI":"10.1145\/1806689.1806782"},{"key":"900_CR6","doi-asserted-by":"publisher","unstructured":"Arvind, V., Srinivasan, S.: On the hardness of the noncommutative determinant. Comput. Complex. 27(1), 1\u201329 (2018). https:\/\/doi.org\/10.1007\/s00037-016-0148-5","DOI":"10.1007\/s00037-016-0148-5"},{"key":"900_CR7","doi-asserted-by":"publisher","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Counting paths and packings in halves. In: Fiat, A., Sanders, P. (eds.) Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7\u20139, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science. Springer, pp. 578\u2013586 (2009). https:\/\/doi.org\/10.1007\/978-3-642-04128-0_52","DOI":"10.1007\/978-3-642-04128-0_52"},{"issue":"20","key":"900_CR8","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1016\/j.ipl.2010.07.005","volume":"110","author":"A Bj\u00f6rklund","year":"2010","unstructured":"Bj\u00f6rklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Evaluation of permanents in rings and semirings. Inf. Process. Lett. 110(20), 867\u2013870 (2010). https:\/\/doi.org\/10.1016\/j.ipl.2010.07.005","journal-title":"Inf. Process. Lett."},{"key":"900_CR9","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\u201329, 2018, pp. 151\u2013164 (2018). https:\/\/doi.org\/10.1145\/3188745.3188902","DOI":"10.1145\/3188745.3188902"},{"key":"900_CR10","unstructured":"Brand, C., Pratt, K.: Parameterized applications of symbolic differentiation of (totally) multilinear polynomials. In: Bansal, N., Merelli, E., Worrell, J. (eds.) 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12\u201316, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 38:1\u201338:19 (2021)"},{"key":"900_CR11","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511623677","volume-title":"Permutation Groups. London Mathematical Society Student Texts","author":"PJ Cameron","year":"1999","unstructured":"Cameron, P.J.: Permutation Groups. London Mathematical Society Student Texts. Cambridge University Press, Cambridge (1999)"},{"key":"900_CR12","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, F.V., Kowalik, L., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., Saurabh, S.: Parameterized Algorithms. Springer, Berlin (2015)"},{"key":"900_CR13","doi-asserted-by":"crossref","unstructured":"Dell, H., Lapinskas, J.: Fine-grained reductions from approximate counting to decision. ACM Trans. Comput. Theory 13(2):8:1\u20138:24 (2021)","DOI":"10.1145\/3442352"},{"key":"900_CR14","doi-asserted-by":"crossref","unstructured":"Dell, H., Lapinskas, J., Meeks, K.: Approximately counting and sampling small witnesses using a colourful decision oracle. In: Chawla, S. (ed.) Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020. SIAM, pp. 2201\u20132211 (2020)","DOI":"10.1137\/1.9781611975994.135"},{"issue":"4","key":"900_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"RA Demillo","year":"1978","unstructured":"Demillo, R.A., Lipton, R.J.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7(4), 193\u2013195 (1978). https:\/\/doi.org\/10.1016\/0020-0190(78)90067-4","journal-title":"Inf. Process. Lett."},{"key":"900_CR16","doi-asserted-by":"publisher","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer (2013). https:\/\/doi.org\/10.1007\/978-1-4471-5559-1","DOI":"10.1007\/978-1-4471-5559-1"},{"issue":"1","key":"900_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1080\/0025570X.1994.11996185","volume":"67","author":"I Fischer","year":"1994","unstructured":"Fischer, I.: Sums of like powers of multivariate linear forms. Math. Mag. 67(1), 59\u201361 (1994). https:\/\/doi.org\/10.1080\/0025570X.1994.11996185","journal-title":"Math. Mag."},{"key":"900_CR18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2019.03.004","author":"D Harvey","year":"2019","unstructured":"Harvey, D., van der Hoeven, J.: Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. J. Complex. (2019). https:\/\/doi.org\/10.1016\/j.jco.2019.03.004","journal-title":"J. Complex."},{"key":"900_CR19","doi-asserted-by":"publisher","first-page":"563","DOI":"10.4007\/annals.2021.193.2.4","volume":"193","author":"D Harvey","year":"2021","unstructured":"Harvey, D., van der Hoeven, J.: Integer multiplication in time $${O}(n\\log n)$$. Ann. Math. 193, 563\u2013617 (2021). https:\/\/doi.org\/10.4007\/annals.2021.193.2.4","journal-title":"Ann. Math."},{"issue":"2","key":"900_CR20","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/s00453-007-9008-7","volume":"52","author":"F H\u00fcffner","year":"2008","unstructured":"H\u00fcffner, F., Wernicke, S., Zichner, T.: Algorithm engineering for color-coding with applications to signaling pathway detection. Algorithmica 52(2), 114\u2013132 (2008). https:\/\/doi.org\/10.1007\/s00453-007-9008-7","journal-title":"Algorithmica"},{"key":"900_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\u201311, 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"},{"key":"900_CR22","doi-asserted-by":"publisher","unstructured":"Koutis, I., Williams, R.: Limits and applications of group algebras for parameterized problems. ACM Trans. Algorithms 12(3):31:1\u201331:18 (2016). https:\/\/doi.org\/10.1145\/2885499","DOI":"10.1145\/2885499"},{"key":"900_CR23","doi-asserted-by":"crossref","unstructured":"Lee, H.: Power sum decompositions of elementary symmetric polynomials. Linear Algebra Applications 492(08) (2015)","DOI":"10.1016\/j.laa.2015.11.018"},{"key":"900_CR24","unstructured":"Mahajan, M., Vinay, V.: Determinant: combinatorics, algorithms, and complexity. Chic. J. Theor. Comput. Sci. (1997). http:\/\/cjtcs.cs.uchicago.edu\/articles\/1997\/5\/contents.html"},{"key":"900_CR25","doi-asserted-by":"publisher","unstructured":"Naor, M., Schulman, L.J., Srinivasan, A.: Splitters and near-optimal derandomization. In: 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, USA, 23\u201325 October 1995. IEEE Computer Society, pp. 182\u2013191 (1995). https:\/\/doi.org\/10.1109\/SFCS.1995.492475","DOI":"10.1109\/SFCS.1995.492475"},{"key":"900_CR26","doi-asserted-by":"publisher","unstructured":"Nisan, N.: Lower bounds for non-commutative computation (extended abstract). In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5\u20138, 1991, New Orleans, Louisiana, USA, pp. 410\u2013418 (1991). https:\/\/doi.org\/10.1145\/103418.103462","DOI":"10.1145\/103418.103462"},{"key":"900_CR27","unstructured":"Pratt, K.: Faster algorithms via waring decompositions. CoRR (2018). arXiv:1807.06194"},{"key":"900_CR28","doi-asserted-by":"publisher","unstructured":"Pratt, K.: Waring rank, parameterized and exact algorithms. In: Zuckerman, D. (ed.) 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9\u201312, 2019. IEEE Computer Society, pp. 806\u2013823 (2019). https:\/\/doi.org\/10.1109\/FOCS.2019.00053","DOI":"10.1109\/FOCS.2019.00053"},{"issue":"1","key":"900_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R Raz","year":"2005","unstructured":"Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non-commutative models. Comput. Complex. 14(1), 1\u201319 (2005). https:\/\/doi.org\/10.1007\/s00037-005-0188-8","journal-title":"Comput. Complex."},{"key":"900_CR30","doi-asserted-by":"crossref","unstructured":"Ryser, H.J.: Combinatorial mathematics. Carus mathematical monographs. Mathematical Association of America; distributed by Wiley (New York, 1963). https:\/\/books.google.co.in\/books?id=wOruAAAAMAAJ","DOI":"10.5948\/UPO9781614440147"},{"key":"900_CR31","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\u201311, 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":"4","key":"900_CR32","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."},{"issue":"3\u20134","key":"900_CR33","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1561\/0400000039","volume":"5","author":"A Shpilka","year":"2010","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci. 5(3\u20134), 207\u2013388 (2010). https:\/\/doi.org\/10.1561\/0400000039","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"900_CR34","first-page":"184","volume":"264","author":"V Strassen","year":"1973","unstructured":"Strassen, V.: Vermeidung von divisionen. Journal f\u00fcr die reine und angewandte Mathematik 264, 184\u2013202 (1973)","journal-title":"Journal f\u00fcr die reine und angewandte Mathematik"},{"key":"900_CR35","unstructured":"Valiant, L.G.: Completeness classes in algebra. In: Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30\u2013May 2, 1979, Atlanta, Georgia, USA, pp. 249\u2013261 (1979)"},{"issue":"4","key":"900_CR36","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1137\/0212043","volume":"12","author":"LG Valiant","year":"1983","unstructured":"Valiant, L.G., Skyum, S., Berkowitz, S., Rackoff, C.: Fast parallel computation of polynomials using few processors. SIAM J. Comput. 12(4), 641\u2013644 (1983). https:\/\/doi.org\/10.1137\/0212043","journal-title":"SIAM J. Comput."},{"key":"900_CR37","doi-asserted-by":"crossref","unstructured":"von\u00a0zur Gathen, J., Gerhard, J.: Modern Computer Algebra, 3rd ed. Cambridge University Press, Cambridge (2013)","DOI":"10.1017\/CBO9781139856065"},{"key":"900_CR38","unstructured":"Williams, R.R.: Counting solutions to polynomial systems via reductions. In: Seidel, R. (ed.) 1st Symposium on Simplicity in Algorithms, SOSA 2018, January 7\u201310, 2018, New Orleans, LA, USA, volume\u00a061 of OASICS. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp. 6:1\u20136:15 (2018)"},{"key":"900_CR39","doi-asserted-by":"publisher","unstructured":"Williams, R.R.: The polynomial method in circuit complexity applied to algorithm design (invited talk). In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014, December 15\u201317, 2014, New Delhi, India, pp. 47\u201360 (2014). https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2014.47","DOI":"10.4230\/LIPIcs.FSTTCS.2014.47"},{"issue":"6","key":"900_CR40","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$${}^{\\text{* }}$$(2$${}^{\\text{ k }}$$) 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":"900_CR41","doi-asserted-by":"publisher","unstructured":"Williams, R.: Algorithms for circuits and circuits for algorithms. In: IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11\u201313, 2014, pp. 248\u2013261 (2014). https:\/\/doi.org\/10.1109\/CCC.2014.33","DOI":"10.1109\/CCC.2014.33"},{"key":"900_CR42","doi-asserted-by":"crossref","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Proceedinsg of the International Symposium on Symbolic and Algebraic Computation, pp. 216\u2013226 (1979)","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00900-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00900-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00900-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,22]],"date-time":"2023-01-22T10:16:47Z","timestamp":1674382607000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00900-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,10]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["900"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00900-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,10]]},"assertion":[{"value":"19 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 November 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 January 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}