Document Open Access Logo

Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials

Authors Cornelius Brand, Kevin Pratt

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2021.38.pdf
  • Filesize: 0.71 MB
  • 19 pages

Document Identifiers

Author Details

Cornelius Brand
  • Charles University, Prague, Czech Republic
Kevin Pratt
  • Carnegie Mellon University, Pittsburgh, PA, USA

Funding

  • Brand, Cornelius: The research was supported by OP RDE project No. CZ.02.2.69/0.0/0.0/ 18_053/0016976 International mobility of research, technical and administrative staff at Charles University.

Acknowledgements

We would like to thank Ryan O'Donnell and several anonymous reviewers for their many helpful comments on earlier drafts of this paper. In particular we thank an anonymous reviewer for suggesting the name "totally multilinear."

Cite AsGet BibTex

Cornelius Brand and Kevin Pratt. Parameterized Applications of Symbolic Differentiation of (Totally) Multilinear Polynomials. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 38:1-38:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ICALP.2021.38

Abstract

We study the following problem and its applications: given a homogeneous degree-d polynomial g as an arithmetic circuit C, and a d × d matrix X whose entries are homogeneous linear polynomials, compute g(∂/∂ x₁, …, ∂/∂ x_n) det X. We show that this quantity can be computed using 2^{ω d}|C|poly(n,d) arithmetic operations, where ω is the exponent of matrix multiplication. In the case that C is skew, we improve this to 4^d|C| poly(n,d) operations, and if furthermore X is a Hankel matrix, to φ^{2d}|C| poly(n,d) operations, where φ = (1+√5)/2 is the golden ratio. Using these observations we give faster parameterized algorithms for the matroid k-parity and k-matroid intersection problems for linear matroids, and faster deterministic algorithms for several problems, including the first deterministic polynomial time algorithm for testing if a linear space of matrices of logarithmic dimension contains an invertible matrix. We also match the runtime of the fastest deterministic algorithm for detecting subgraphs of bounded pathwidth with a new and simple approach. Our approach generalizes several previous methods in parameterized algorithms and can be seen as a relaxation of Waring rank based methods [Pratt, FOCS19].

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Parameterized Algorithms
  • Algebraic Algorithms
  • Longest Cycle
  • Matroid Parity

Metrics

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

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  2. Nima Anari and Shayan Oveis Gharan. A generalization of permanent inequalities and applications in counting and optimization. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 384-396. ACM, 2017. Google Scholar
  3. Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei. Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes. In Conference on Learning Theory, pages 103-115, 2016. Google Scholar
  4. Nima Anari, Shayan Oveis Gharan, and Cynthia Vinzant. Log-concave polynomials, entropy, and a deterministic approximation algorithm for counting bases of matroids. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 35-46. IEEE, 2018. Google Scholar
  5. Nima Anari, Shayan Oveis Gharan, Amin Saberi, and Mohit Singh. Nash social welfare, matrix permanent, and stable polynomials. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  6. Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. Fast exact algorithms using Hadamard product of polynomials. In Arkadev Chattopadhyay and Paul Gastin, editors, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India, volume 150 of LIPIcs, pages 9:1-9:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2019.9.
  7. Vikraman Arvind, Abhranil Chatterjee, Rajit Datta, and Partha Mukhopadhyay. On explicit branching programs for the rectangular determinant and permanent polynomials. Chic. J. Theor. Comput. Sci., 2020, 2020. URL: http://cjtcs.cs.uchicago.edu/articles/2020/2/contents.html.
  8. Alexander I Barvinok. New algorithms for lineark-matroid intersection and matroid k-parity problems. Mathematical Programming, 69(1-3):449-470, 1995. Google Scholar
  9. Alexander I Barvinok. Two algorithmic results for the traveling salesman problem. Mathematics of Operations Research, 21(1):65-84, 1996. Google Scholar
  10. Andreas Björklund. Determinant sums for undirected hamiltonicity. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 173-182, 2010. URL: https://doi.org/10.1109/FOCS.2010.24.
  11. Cornelius Brand. Patching colors with tensors. In 27th Annual European Symposium on Algorithms, ESA 2019, September 09-11, 2019, Munich, Germany, 2019. Google Scholar
  12. 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.
  13. Peter Bürgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory. Journal of the American Mathematical Society, 32(1):163-193, 2019. Google Scholar
  14. Luca Chiantini, Jonathan D Hauenstein, Christian Ikenmeyer, Joseph M Landsberg, and Giorgio Ottaviani. Polynomials and the exponent of matrix multiplication. Bulletin of the London Mathematical Society, 50(3):369-389, 2018. Google Scholar
  15. Aldo Conca. Straightening law and powers of determinantal ideals of Hankel matrices. Advances in Mathematics, 138(2):263-292, 1998. Google Scholar
  16. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  17. Marek Cygan, Harold N Gabow, and Piotr Sankowski. Algorithmic applications of baur-strassen’s theorem: Shortest cycles, diameter, and matchings. Journal of the ACM (JACM), 62(4):1-30, 2015. Google Scholar
  18. Jack Edmonds. Systems of distinct representatives and linear algebra. J. Res. Nat. Bur. Standards Sect. B, 71(4):241-245, 1967. Google Scholar
  19. Richard Ehrenborg and Gian-Carlo Rota. Apolarity and Canonical Forms for Homogeneous Polynomials. European Journal of Combinatorics, 14(3):157–181, 1993. URL: https://doi.org/10.1006/eujc.1993.1022.
  20. Fedor V. Fomin, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh. Efficient computation of representative families with applications in parameterized and exact algorithms. J. ACM, 63(4):29:1-29:60, 2016. URL: https://doi.org/10.1145/2886094.
  21. Fedor V Fomin, Daniel Lokshtanov, and Saket Saurabh. Efficient computation of representative sets with applications in parameterized and exact algorithms. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 142-151. SIAM, 2014. Google Scholar
  22. Ankit Garg, Leonid Gurvits, Rafael Oliveira, and Avi Wigderson. Operator scaling: theory and applications. Foundations of Computational Mathematics, pages 1-68, 2019. Google Scholar
  23. David G Glynn. Permanent formulae from the Veronesean. Designs, codes and cryptography, 68(1-3):39-47, 2013. Google Scholar
  24. Leonid Gurvits. Classical deterministic complexity of Edmonds' problem and quantum entanglement. In Proceedings of the Thirty-fifth Annual ACM Symposium on Theory of Computing, STOC '03, pages 10-19, New York, NY, USA, 2003. ACM. URL: https://doi.org/10.1145/780542.780545.
  25. Leonid Gurvits. On the complexity of mixed discriminants and related problems. In International Symposium on Mathematical Foundations of Computer Science, pages 447-458. Springer, 2005. Google Scholar
  26. Leonid Gurvits. Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. In Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 417-426. ACM, 2006. Google Scholar
  27. Leonid Gurvits. Van der waerden/schrijver-valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all. The electronic journal of combinatorics, 15(1):66, 2008. Google Scholar
  28. Gregory Z. Gutin, Felix Reidl, Magnus Wahlström, and Meirav Zehavi. Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials. J. Comput. Syst. Sci., 95:69-85, 2018. URL: https://doi.org/10.1016/j.jcss.2018.01.004.
  29. Anthony Iarrobino and Vassil Kanev. Power sums, Gorenstein algebras, and determinantal loci. Springer Science & Business Media, 1999. Google Scholar
  30. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. Google Scholar
  31. Ioannis Koutis and Ryan Williams. Limits and applications of group algebras for parameterized problems. In Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, pages 653-664, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_54.
  32. Joseph M Landsberg. Tensors: geometry and applications. Representation theory, 381:402, 2012. Google Scholar
  33. François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296-303, 2014. Google Scholar
  34. László Lovász. On determinants, matchings, and random algorithms. Fundamentals of Computation Theory, pages 565-574, 1979. Google Scholar
  35. Meena Mahajan and V Vinay. A combinatorial algorithm for the determinant. In In Proceedings of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms. Citeseer, 1997. Google Scholar
  36. Dániel Marx. A parameterized view on matroid optimization problems. Theor. Comput. Sci., 410(44):4471-4479, 2009. URL: https://doi.org/10.1016/j.tcs.2009.07.027.
  37. Kevin Pratt. Waring rank, parameterized and exact algorithms. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, MD, USA, November 9-12, 2019, 2019. Google Scholar
  38. Masoumeh Sepideh Shafiei. Apolarity for determinants and permanents of generic matrices. Journal of Commutative Algebra, 7(1):89-123, 2015. Google Scholar
  39. J.J. Sylvester. On the principles of the calculus of forms. Cambridge and Dublin Mathematical Journal, 7:52-97, 1852. Google Scholar
  40. Dekel Tsur. Faster deterministic parameterized algorithm for k-Path. Theoretical Computer Science, 790:96–104, 2019. URL: https://doi.org/10.1016/j.tcs.2019.04.024.
  41. 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.
  42. Michał Włodarczyk. Clifford algebras meet tree decompositions. Algorithmica, 81(2):497-518, 2019. Google Scholar
  43. Meirav Zehavi. Mixing color coding-related techniques. In Algorithms-ESA 2015, pages 1037-1049. Springer, 2015. 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