Document Open Access Logo

On Isoperimetric Profiles and Computational Complexity

Authors Pavel Hrubes, Amir Yehudayoff

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.89.pdf
  • Filesize: 470 kB
  • 12 pages

Document Identifiers

Author Details

Pavel Hrubes
Amir Yehudayoff

Cite As Get BibTex

Pavel Hrubes and Amir Yehudayoff. On Isoperimetric Profiles and Computational Complexity. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 89:1-89:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.89

Abstract

The isoperimetric profile of a graph is a function that measures, for an integer k, the size of the smallest edge boundary over all sets of vertices of size k. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, but our main result is in algebraic complexity.

We prove a sharp super-polynomial separation between monotone arithmetic circuits and monotone arithmetic branching programs. This shows that the classical simulation of arithmetic circuits by arithmetic branching programs by Valiant, Skyum, Berkowitz, and Rackoff (1983) cannot be improved, as long as it preserves monotonicity.

A key ingredient in the proof is an accurate analysis of the isoperimetric profile of finite full binary trees. We show that the isoperimetric profile of a full binary tree constantly fluctuates between one and almost the depth of the tree.

Subject Classification

Keywords
  • Monotone computation
  • separations
  • communication complexity
  • isoperimetry

Metrics

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

References

  1. M. Agrawal and V. Vinay. Arithmetic circuits: A chasm at depth four. In FOCS, pages 67-75, 2008. Google Scholar
  2. S. Arora and B. Barak. Computational complexity: a modern approach. Cambridge University Press, 2009. Google Scholar
  3. B. S. Bharadwaj, L. S. Chandran, and A. Das. Isoperimetric problem and meta-fibonacci sequences. In Computing and Combinatorics, pages 22-30. Springer, 2008. Google Scholar
  4. A. Borodin, A. A. Razborov, and R. Smolensky. On lower bounds for read-k-times branching programs. Computational Complexity, 3(1):1-18, 1993. Google Scholar
  5. P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic complexity theory, volume 315. Springer Science and Business Media, 1997. Google Scholar
  6. H. Fournier, N. Limaye, G. Malod, and S. Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In STOC, pages 128-135, 2014. Google Scholar
  7. J. von zur Gathen. Algebraic complexity theory. Annual review of computer science, 3:317-347, 1988. Google Scholar
  8. A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Arithmetic circuits: A chasm at depth three. In FOCS, pages 578-587, 2013. Google Scholar
  9. A. Gupta, P. Kamath, N. Kayal, and R. Saptharishi. Approaching the chasm at depth four. Journal of the ACM, 61(6):33, 2014. Google Scholar
  10. P. Hrubes and A. Yehudayoff. Monotone separations for constant degree polynomials. Information Processing Letters, 110(1):1-3, 2009. Google Scholar
  11. L. Hyafil. On the parallel evaluation of multivariate polynomials. SIAM J. Comput., 8(2):120-123, 1979. Google Scholar
  12. S. Jukna. Boolean function complexity: advances and frontiers, volume 27. Springer Science and Business Media, 2012. Google Scholar
  13. P. Koiran. Arithmetic circuits: The chasm at depth four gets wider. Theoretical Computer Science, 448:56-65, 2012. Google Scholar
  14. M. Kumar and S. Saraf. The limits of depth reduction for arithmetic formulas: It’s all about the top fan-in. In STOC, pages 136-145, 2014. Google Scholar
  15. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. Google Scholar
  16. F. Morgan. Manifolds with density. Notices of the AMS, pages 853-858, 2005. Google Scholar
  17. N. Nisan. Lower bounds for non-commutative computation. In STOC, pages 410-418, 1991. Google Scholar
  18. C. H. Papadimitriou and M. Sipser. Communication complexity. In STOC, pages 196-200, 1982. Google Scholar
  19. R. Raz and A. Yehudayoff. Multilinear formulas, maximal-partition discrepancy and mixed-sources extractors. J. Comput. Syst. Sci., 77(1):167-190, 2011. Google Scholar
  20. E. Shamir and M. Snir. Lower bounds on the number of multiplications and the number of additions in monotone computations. Technical Report RC-6757, IBM, 1977. Google Scholar
  21. A. Shpilka and A. Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Found. Trends Theor. Comput. Sci., 5:207-388, 2010. URL: 10.1561/0400000039, URL: http://dx.doi.org/10.1561/0400000039.
  22. S. Tavenas. Improved bounds for reduction to depth 4 and depth 3. Information and Computation, 240:2-11, 2015. Google Scholar
  23. L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. on Computing, 12(4):641-644, 1983. Google Scholar
  24. A. C. Yao. Some complexity questions related to distributive computing (preliminary report). In STOC, pages 209-213, 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