Document Open Access Logo

Fast Exact Algorithms Using Hadamard Product of Polynomials

Authors V. Arvind, Abhranil Chatterjee, Rajit Datta, Partha Mukhopadhyay

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2019.9.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Author Details

V. Arvind
  • Institute of Mathematical Sciences (HBNI), Chennai, India
Abhranil Chatterjee
  • Institute of Mathematical Sciences (HBNI), Chennai, India
Rajit Datta
  • Chennai Mathematical Institute, Chennai, India
Partha Mukhopadhyay
  • Chennai Mathematical Institute, Chennai, India

Acknowledgements

We thank anonymous reviewers for their comments on an earlier version of this paper. We are particularly grateful to an anonymous reviewer for pointing out the combinatorial applications of Theorem 1 in exact counting.

Cite AsGet BibTex

V. Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Fast Exact Algorithms Using Hadamard Product of Polynomials. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.FSTTCS.2019.9

Abstract

Let C be an arithmetic circuit of poly(n) size given as input that computes a polynomial f in F[X], where X={x_1,x_2,...,x_n} and F is any field where the field arithmetic can be performed efficiently. We obtain new algorithms for the following two problems first studied by Koutis and Williams [Ioannis Koutis, 2008; Ryan Williams, 2009; Ioannis Koutis and Ryan Williams, 2016]. - (k,n)-MLC: Compute the sum of the coefficients of all degree-k multilinear monomials in the polynomial f. - k-MMD: Test if there is a nonzero degree-k multilinear monomial in the polynomial f. Our algorithms are based on the fact that the Hadamard product f o S_{n,k}, is the degree-k multilinear part of f, where S_{n,k} is the k^{th} elementary symmetric polynomial. - For (k,n)-MLC problem, we give a deterministic algorithm of run time O^*(n^(k/2+c log k)) (where c is a constant), answering an open question of Koutis and Williams [Ioannis Koutis and Ryan Williams, 2016]. As corollaries, we show O^*(binom{n}{downarrow k/2})-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating Set, m-Dimensional k-Matching. - For k-MMD problem, we give a randomized algorithm of run time 4.32^k * poly(n,k). Our algorithm uses only poly(n,k) space. This matches the run time of a recent algorithm [Cornelius Brand et al., 2018] for k-MMD which requires exponential (in k) space. Other results include fast deterministic algorithms for (k,n)-MLC and k-MMD problems for depth three circuits.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation
Keywords
  • Hadamard Product
  • Multilinear Monomial Detection and Counting
  • Rectangular Permanent
  • Symmetric Polynomial

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-Coding. J. ACM, 42(4):844-856, 1995. URL: https://doi.org/10.1145/210332.210337.
  2. Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Fast Exact Algorithms Using Hadamard Product of Polynomials. CoRR, abs/1807.04496, 2018. URL: http://arxiv.org/abs/1807.04496.
  3. Vikraman Arvind, Pushkar S. Joglekar, and Srikanth Srinivasan. 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-17, 2009, IIT Kanpur, India, pages 25-36, 2009. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2304.
  4. Vikraman Arvind and Srikanth Srinivasan. On the hardness of the noncommutative determinant. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 677-686, 2010. URL: https://doi.org/10.1145/1806689.1806782.
  5. Vikraman Arvind and Srikanth Srinivasan. On the hardness of the noncommutative determinant. Computational Complexity, 27(1):1-29, 2018. URL: https://doi.org/10.1007/s00037-016-0148-5.
  6. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Counting Paths and Packings in Halves. In Amos Fiat and Peter Sanders, editors, Algorithms - ESA 2009, pages 578-586, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  7. Andreas Björklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. Evaluation of permanents in rings and semirings. Inf. Process. Lett., 110(20):867-870, 2010. URL: https://doi.org/10.1016/j.ipl.2010.07.005.
  8. Cornelius Brand, Holger Dell, and Thore Husfeldt. 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, pages 151-164, 2018. URL: https://doi.org/10.1145/3188745.3188902.
  9. Richard A. Demillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Information Processing Letters, 7(4):193-195, 1978. URL: https://doi.org/10.1016/0020-0190(78)90067-4.
  10. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: https://doi.org/10.1007/978-1-4471-5559-1.
  11. Ismor Fischer. Sums of Like Powers of Multivariate Linear Forms. Mathematics Magazine, 67(1):59-61, 1994. URL: https://doi.org/10.1080/0025570X.1994.11996185.
  12. Falk Hüffner, Sebastian Wernicke, and Thomas Zichner. Algorithm Engineering for Color-Coding with Applications to Signaling Pathway Detection. Algorithmica, 52(2):114-132, 2008. URL: https://doi.org/10.1007/s00453-007-9008-7.
  13. Ioannis Koutis. 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, pages 575-586, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_47.
  14. Ioannis Koutis and Ryan Williams. LIMITS and applications of group algebras for parameterized problems. ACM Trans. Algorithms, 12(3):31:1-31:18, 2016. URL: https://doi.org/10.1145/2885499.
  15. Hwangrae Lee. Power Sum Decompositions of Elementary Symmetric Polynomials. In Linear Algebra and its Applications, volume 492. Elsevier, August 2015. Google Scholar
  16. Kevin Pratt. Faster Algorithms via Waring Decompositions. CoRR, abs/1807.06194, 2018. URL: http://arxiv.org/abs/1807.06194.
  17. H.J. Ryser. Combinatorial mathematics. Carus mathematical monographs. Mathematical Association of America; distributed by Wiley [New York, 1963. URL: https://books.google.co.in/books?id=wOruAAAAMAAJ.
  18. Jacob T. Schwartz. Fast Probabilistic algorithm for verification of polynomial identities. J. ACM., 27(4):701-717, 1980. Google Scholar
  19. Amir Shpilka and Amir Yehudayoff. Arithmetic Circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5(3-4):207-388, 2010. URL: https://doi.org/10.1561/0400000039.
  20. Leslie G. Valiant, Sven Skyum, S. Berkowitz, and Charles Rackoff. Fast Parallel Computation of Polynomials Using Few Processors. SIAM J. Comput., 12(4):641-644, 1983. URL: https://doi.org/10.1137/0212043.
  21. Richard Ryan Williams. 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-17, 2014, New Delhi, India, pages 47-60, 2014. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2014.47.
  22. Ryan Williams. Finding paths of length k in O^*(2^k) time. Inf. Process. Lett., 109(6):315-318, 2009. URL: https://doi.org/10.1016/j.ipl.2008.11.004.
  23. Ryan Williams. Algorithms for Circuits and Circuits for Algorithms. In IEEE 29th Conference on Computational Complexity, CCC 2014, Vancouver, BC, Canada, June 11-13, 2014, pages 248-261, 2014. URL: https://doi.org/10.1109/CCC.2014.33.
  24. R. Zippel. Probabilistic algorithms for sparse polynomials. In Proc. of the Int. Sym. on Symbolic and Algebraic Computation, pages 216-226, 1979. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact