Document Open Access Logo

A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas

Authors Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.36.pdf
  • Filesize: 0.54 MB
  • 13 pages

Document Identifiers

Author Details

Suryajith Chillara
  • Department of CSE, IIT Bombay, Mumbai, India
Nutan Limaye
  • Department of CSE, IIT Bombay, Mumbai, India
Srikanth Srinivasan
  • Department of Mathematics, IIT Bombay, Mumbai, India

Cite AsGet BibTex

Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.36

Abstract

We show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. Formally, for any s = s(n) = n^{O(1)} and any delta>0, we construct explicit families of multilinear polynomials P_n in F[x_1,...,x_n] that have multilinear formulas of size s and depth three but no multilinear formulas of size s^{1/2-delta} and depth o(log n/log log n). As far as we know, this is the first such result for an algebraic model of computation. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using epsilon-biased spaces.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Algebraic circuit complexity
  • Multilinear formulas
  • Lower Bounds

Metrics

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

References

  1. M. Ajtai. Σ₁¹-formulae on finite structures. Annals of Pure and Applied Logic, 24(1):1-48, 1983. URL: http://dx.doi.org/10.1016/0168-0072(83)90038-6.
  2. Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta. Simple construction of almost k-wise independent random variables. Random Struct. Algorithms, 3(3):289-304, 1992. URL: http://dx.doi.org/10.1002/rsa.3240030308.
  3. Noga Alon, Mrinal Kumar, and Ben Lee Volk. Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits, 2017. URL: https://mrinalkr.bitbucket.io/papers/synt-multilinear.pdf.
  4. Kazuyuki Amano. k-subgraph isomorphism on AC^0 circuits. Computational Complexity, 19(2):183-210, 2010. URL: http://dx.doi.org/10.1007/s00037-010-0288-y.
  5. Maria Luisa Bonet and Samuel R. Buss. Size-depth tradeoffs for boolean formulae. Information Processing Letters, 49(3):151-155, 1994. URL: http://dx.doi.org/10.1016/0020-0190(94)90093-0.
  6. Richard P. Brent. The parallel evaluation of general arithmetic expressions. Journal of the ACM, 21(2):201-206, 1974. URL: http://dx.doi.org/10.1145/321812.321815.
  7. Suryajith Chillara, Christian Engels, Nutan Limaye, and Srikanth Srinivasan. A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. Electronic Colloquium on Computational Complexity (ECCC), 25:066, 2018. URL: https://eccc.weizmann.ac.il/report/2018/066/s.
  8. Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan. Small-depth multilinear formula lower bounds for iterated matrix multiplication, with applications. In STACS, volume 96 of LIPIcs, pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  9. Anindya De, Omid Etesami, Luca Trevisan, and Madhur Tulsiani. Improved pseudorandom generators for depth 2 circuits. In APPROX-RANDOM, volume 6302 of Lecture Notes in Computer Science, pages 504-517. Springer, 2010. Google Scholar
  10. Zeev Dvir and Shachar Lovett. Subspace evasive sets. In STOC, pages 351-358. ACM, 2012. Google Scholar
  11. Zeev Dvir, Guillaume Malod, Sylvain Perifel, and Amir Yehudayoff. Separating multilinear branching programs and formulas. In proceedings of Symposium on Theory of Computing (STOC), pages 615-624, 2012. URL: http://dx.doi.org/10.1145/2213977.2214034.
  12. Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory, 17(1):13-27, Dec 1984. URL: http://dx.doi.org/10.1007/BF01744431.
  13. J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117:285-306, 1965. URL: http://www.jstor.org/stable/1994208.
  14. J. Håstad. Computational limitations of small-depth circuits. ACM doctoral dissertation award. MIT Press, 1987. URL: https://books.google.co.in/books?id=_h0ZAQAAIAAJ.
  15. Pavel Hrubeš and Amir Yehudayoff. Homogeneous formulas and symmetric polynomials. Computational Complexity, 20(3):559-578, 2011. Google Scholar
  16. Russell Impagliazzo and Valentine Kabanets. Constructive proofs of concentration bounds. In APPROX-RANDOM, volume 6302 of Lecture Notes in Computer Science, pages 617-631. Springer, 2010. Google Scholar
  17. Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In proceedings of Symposium on Theoretical Aspects of Computer Science (STACS), pages 46:1-46:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2016.46.
  18. P. M. Lewis, R. E. Stearns, and J. Hartmanis. Hierarchies of memory limited computations. In 6th Annual Symposium on Switching Circuit Theory and Logical Design (SWCT 1965)(FOCS), volume 00, pages 179-190, 10 1965. URL: http://dx.doi.org/10.1109/FOCS.1965.11.
  19. Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications. SIAM J. Comput., 22(4):838-856, 1993. URL: http://dx.doi.org/10.1137/0222053.
  20. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. URL: http://dx.doi.org/10.1007/BF01294256.
  21. Ran Raz. Multilinear-NC² ≠ multilinear-NC¹. In proceedings of Foundations of Computer Science (FOCS), pages 344-351, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.42.
  22. Ran Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(1):121-135, 2006. URL: http://dx.doi.org/10.4086/toc.2006.v002a006.
  23. Ran Raz, Amir Shpilka, and Amir Yehudayoff. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM Journal of Computing, 38(4):1624-1647, 2008. URL: http://dx.doi.org/10.1137/070707932.
  24. Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17(4):515-535, 2008. URL: http://dx.doi.org/10.1007/s00037-008-0254-0.
  25. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171-207, 2009. URL: http://dx.doi.org/10.1007/s00037-009-0270-8.
  26. Benjamin Rossman. Average-case Complexity of Detecting Cliques. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2010. AAI0823246. Google Scholar
  27. Ramprasad Saptharishi. A survey of lower bounds in arithmetic circuit complexity. Github survey, 2015. URL: https://github.com/dasarpmar/lowerbounds-survey/releases/.
  28. Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open questions. Foundations and Trends in Theoretical Computer Science, 5:207-388, March 2010. URL: http://dx.doi.org/10.1561/0400000039.
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