Document Open Access Logo

On the Complexity of Partial Derivatives

Authors Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, Stéphan Thomassé

PDF
Thumbnail PDF

File

LIPIcs.STACS.2017.37.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Ignacio Garcia-Marco
Pascal Koiran
Timothée Pecatte
Stéphan Thomassé

Cite As Get BibTex

Ignacio Garcia-Marco, Pascal Koiran, Timothée Pecatte, and Stéphan Thomassé. On the Complexity of Partial Derivatives. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.STACS.2017.37

Abstract

The method of partial derivatives is one of the most successful lower bound methods for arithmetic circuits. It uses as a complexity measure the dimension of the span of the partial derivatives of a polynomial. In this paper, we consider this complexity measure as a computational problem: for an input polynomial given as the sum of its nonzero monomials, what is the complexity of computing the dimension of its space of partial derivatives? 

We show that this problem is #P-hard and we ask whether it belongs to #P. We analyze the "trace method", recently used in combinatorics and in algebraic complexity to lower bound the rank of certain matrices. We show that this method provides a polynomial-time computable lower bound on the dimension of the span of partial derivatives, and from this method we derive closed-form lower bounds. We leave as an open problem the existence of an approximation algorithm with reasonable performance guarantees.

Subject Classification

Keywords
  • counting complexity
  • simplicial complex
  • lower bounds
  • arithmetic circuits

Metrics

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

References

  1. Noga Alon. Perturbed identity matrices have high rank: Proof and applications. Combinatorics, Probability and Computing, 18(1-2):3-15, 2009. Google Scholar
  2. Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial derivatives in arithmetic complexity and beyond. Found. Trends Theor. Comput. Sci., 6(1-2):front matter, 1-138 (2011), 2010. Google Scholar
  3. Martin Dyer, Alan Frieze, and Mark Jerrum. On counting independent sets in sparse graphs. SIAM J. Comput., 31(5):1527-1541, 2002. Google Scholar
  4. Martin Dyer and Catherine Greenhill. On Markov chains for independent sets. J. Algorithms, 35(1):17-49, 2000. Google Scholar
  5. Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan. The shifted partial derivative complexity of elementary symmetric polynomials. In Mathematical foundations of computer science 2015. Part II, volume 9235 of Lecture Notes in Comput. Sci., pages 324-335. Springer, Heidelberg, 2015. Google Scholar
  6. D. H. Gottlieb. A certain class of incidence matrices. Proc. Amer. Math. Soc., 17:1233-1237, 1966. Google Scholar
  7. Catherine Greenhill. The complexity of counting colourings and independent sets in sparse graphs and hypergraphs. Comput. Complexity, 9(1):52-72, 2000. Google Scholar
  8. Christopher J. Hillar and Lek-Heng Lim. Most tensor problems are NP-hard. J. ACM, 60(6):Art. 45, 39, 2013. Google Scholar
  9. Neeraj Kayal. Affine projections of polynomials. In STOC'12 - Proceedings of the 2012 ACM Symposium on Theory of Computing, pages 643-661. ACM, New York, 2012. Google Scholar
  10. Neeraj Kayal, Nutan Limaye, Saha Chiranjib, and Sudarshan Srinivasan. An exponential lower bound for homogeneous depth four arithmetic formulas. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 61-70. IEEE, 2004. Google Scholar
  11. Neeraj Kayal and Chandan Saha. Lower bounds for depth three arithmetic circuits with small bottom fanin. In 30th Conference on Computational Complexity, volume 33 of LIPIcs. Leibniz Int. Proc. Inform., pages 158-182. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015. Google Scholar
  12. Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, Cambridge, 1997. Google Scholar
  13. Michael Luby and Eric Vigoda. Approximately counting up to four. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 682-687. ACM, 1997. Google Scholar
  14. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Comput. Complexity, 6(3):217-234, 1996/97. Google Scholar
  15. J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput., 12(4):777-788, 1983. Google Scholar
  16. Bjarke Hammersholt Roune and Eduardo Sáenz-de Cabezón. Complexity and algorithms for Euler characteristic of simplicial complexes. J. Symbolic Comput., 50:170-196, 2013. Google Scholar
  17. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. URL: https://github.com/dasarpmar/lowerbounds-survey/releases.
  18. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5(3-4):207-388, 2010. Google Scholar
  19. Salil P. Vadhan. The complexity of counting in sparse, regular, and planar graphs. SIAM J. Comput., 31(2):398-427 (electronic), 2001. Google Scholar
  20. L. G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189-201, 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 About DROPS Imprint Privacy Contact