Document Open Access Logo

Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits

Authors Neeraj Kayal, Vineet Nair, Chandan Saha

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.46.pdf
  • Filesize: 0.72 MB
  • 15 pages

Document Identifiers

Author Details

Neeraj Kayal
Vineet Nair
Chandan Saha

Cite As Get BibTex

Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.46

Abstract

We show an exponential separation between two well-studied models of algebraic computation, namely read-once oblivious algebraic branching programs (ROABPs) and multilinear depth three circuits. In particular we show the following: 

1. There exists an explicit n-variate polynomial computable by linear sized multilinear depth three circuits (with only two product gates) such that every ROABP computing it requires 2^{Omega(n)} size.

2. Any multilinear depth three circuit computing IMM_{n,d} (the iterated matrix multiplication polynomial formed by multiplying d, n * n symbolic matrices) has n^{Omega(d)} size. IMM_{n,d} can be easily computed by a poly(n,d) sized ROABP.

3. Further, the proof of 2 yields an exponential separation between multilinear depth four and multilinear depth three circuits: There is an explicit n-variate, degree d polynomial computable by a poly(n,d) sized multilinear depth four circuit such that any multilinear depth three circuit computing it has size n^{Omega(d)}. This improves upon the quasi-polynomial separation result by Raz and Yehudayoff [2009] between these two models. 

The hard polynomial in 1 is constructed using a novel application of expander graphs in conjunction with the evaluation dimension measure used previously in Nisan [1991], Raz [2006,2009], Raz and Yehudayoff [2009], and Forbes and Shpilka [2013], while 2 is proved via a new adaptation of the dimension of the partial derivatives measure used by Nisan and Wigderson [1997]. Our lower bounds hold over any field.

Subject Classification

Keywords
  • multilinear depth three circuits
  • read-once oblivious algebraic branching programs
  • evaluation dimension
  • skewed partial derivatives
  • expander graphs,

Metrics

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

References

  1. Manindra Agrawal. Proving lower bounds via pseudo-random generators. In FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science, 25th International Conference, Hyderabad, India, December 15-18, 2005, Proceedings, pages 92-105, 2005. URL: http://dx.doi.org/10.1007/11590156_6.
  2. Manindra Agrawal, Rohit Gurjar, Arpita Korwar, and Nitin Saxena. Hitting-sets for ROABP and sum of set-multilinear circuits. SIAM J. Comput., 44(3):669-697, 2015. URL: http://dx.doi.org/10.1137/140975103.
  3. Manindra Agrawal, Chandan Saha, and Nitin Saxena. Quasi-polynomial hitting-set for set-depth-Δ formulas. In Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 321-330, 2013. Google Scholar
  4. Xi Chen, Neeraj Kayal, and Avi Wigderson. Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends in Theoretical Computer Science, 6(1-2):1-138, 2011. Google Scholar
  5. Rafael Mendes de Oliveira, Amir Shpilka, and Ben Lee Volk. Subexponential size hitting sets for bounded depth multilinear formulas. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 304-322, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.304.
  6. Richard A. DeMillo and Richard J. Lipton. A probabilistic remark on algebraic program testing. Inf. Process. Lett., 7(4):193-195, 1978. URL: http://dx.doi.org/10.1016/0020-0190(78)90067-4.
  7. Zeev Dvir, Guillaume Malod, Sylvain Perifel, and Amir Yehudayoff. Separating multilinear branching programs and formulas. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19-22, 2012, pages 615-624, 2012. URL: http://dx.doi.org/10.1145/2213977.2214034.
  8. Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. SIAM J. Comput., 39(4):1279-1293, 2009. URL: http://dx.doi.org/10.1137/080735850.
  9. Michael A. Forbes, Ramprasad Saptharishi, and Amir Shpilka. Hitting sets for multilinear read-once algebraic branching programs, in any order. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014, pages 867-875, 2014. Google Scholar
  10. Michael A. Forbes and Amir Shpilka. Quasipolynomial-time identity testing of non-commutative and read-once oblivious algebraic branching programs. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 243-252, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.34.
  11. Hervé Fournier, Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In STOC, pages 128-135, 2014. Google Scholar
  12. Ankit Gupta, Pritish Kamath, Neeraj Kayal, and Ramprasad Saptharishi. Arithmetic circuits: A chasm at depth three. In Foundations of Computer Science (FOCS), pages 578-587, 2013. Google Scholar
  13. Rohit Gurjar, Arpita Korwar, Nitin Saxena, and Thomas Thierauf. Deterministic identity testing for sum of read-once oblivious arithmetic branching programs. In 30th Conference on Computational Complexity, CCC 2015, June 17-19, 2015, Portland, Oregon, USA, pages 323-346, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CCC.2015.323.
  14. Philip Hall. On representatives of subsets. J. London Math. Soc., 10(1):26-30, 1935. Google Scholar
  15. Joos Heintz and Claus-Peter Schnorr. Testing polynomials which are easy to compute (extended abstract). In Proceedings of the 12th Annual ACM Symposium on Theory of Computing, April 28-30, 1980, Los Angeles, California, USA, pages 262-272, 1980. URL: http://dx.doi.org/10.1145/800141.804674.
  16. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006. Google Scholar
  17. Valentine Kabanets and Russell Impagliazzo. Derandomizing polynomial identity tests means proving circuit lower bounds. Computational Complexity, 13(1-2):1-46, 2004. URL: http://dx.doi.org/10.1007/s00037-004-0182-6.
  18. Erich Kaltofen. Factorization of Polynomials Given by Straight-Line Programs. In Randomness and Computation, pages 375-412. JAI Press, 1989. Google Scholar
  19. Neeraj Kayal, Vineet Nair, and Chandan Saha. Separation between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. Electronic Colloquium on Computational Complexity (ECCC), 22:154, 2015. URL: http://eccc.hpi-web.de/report/2015/154.
  20. Neeraj Kayal, Chandan Saha, and Sébastien Tavenas. On the size of homogeneous and of depth four formulas with low individual degree. Electronic Colloquium on Computational Complexity (ECCC), 22:181, 2015. URL: http://eccc.hpi-web.de/report/2015/181.
  21. Neeraj Kayal and Ramprasad Saptharishi. A selection of lower bounds for arithmetic circuits. Perspectives in Computational Complexity, 2014. Google Scholar
  22. Meena Mahajan and V. Vinay. Determinant: Combinatorics, algorithms, and complexity. Chicago J. Theor. Comput. Sci., 1997, 1997. URL: http://cjtcs.cs.uchicago.edu/articles/1997/5/contents.html.
  23. Noam Nisan. Lower bounds for non-commutative computation (extended abstract). In Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA, pages 410-418, 1991. URL: http://dx.doi.org/10.1145/103418.103462.
  24. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  25. Noam Nisan and Avi Wigderson. Lower bounds on arithmetic circuits via partial derivatives. Computational Complexity, 6(3):217-234, 1997. Available at URL: http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NW96/final.pdf.
  26. Ran Raz. Separation of multilinear circuit and formula size. Theory of Computing, 2(1):121-135, 2006. Google Scholar
  27. Ran Raz. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 56(2), 2009. Google Scholar
  28. Ran Raz and Amir Yehudayoff. Balancing syntactically multilinear arithmetic circuits. Computational Complexity, 17(4):515-535, 2008. Google Scholar
  29. Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. Computational Complexity, 18(2):171-207, 2009. Google Scholar
  30. Ramprasad Saptharishi. Recent progress on arithmetic circuit lower bounds. Bulletin of the EATCS, 114, 2014. Google Scholar
  31. Nitin Saxena. Progress on polynomial identity testing. Bulletin of the EATCS, 99:49-79, 2009. Google Scholar
  32. Nitin Saxena. Progress on polynomial identity testing - II. Electronic Colloquium on Computational Complexity (ECCC), 20:186, 2013. Google Scholar
  33. Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM, 27(4):701-717, 1980. URL: http://dx.doi.org/10.1145/322217.322225.
  34. 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.
  35. W.T. Tutte. The Factorization of Linear Graphs. J. London Math. Soc., 22:107-111, 1947. Google Scholar
  36. L. G. Valiant. Completeness Classes in Algebra. In STOC'79: Proceedings of the eleventh annual ACM symposium on Theory of computing, pages 249-261, New York, NY, USA, 1979. ACM Press. Google Scholar
  37. Richard Zippel. Probabilistic algorithms for sparse polynomials. In Symbolic and Algebraic Computation, EUROSAM'79, An International Symposiumon Symbolic and Algebraic Computation, Marseille, France, June 1979, Proceedings, pages 216-226, 1979. URL: http://dx.doi.org/10.1007/3-540-09519-5_73.
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