On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models

• Autorzy: Ghosal Purnata , Raghavendra Rao B. V.

Identyfikatory

DOI

10.3233/FI-2020-1980

• Języki publikacji: EN

Abstrakty

EN

We consider the problem of obtaining parameterized lower bounds for the size of arithmetic circuits computing polynomials with the degree of the polynomial as the parameter. We consider the following special classes of multilinear algebraic branching programs: 1) Read Once Oblivious Branching Programs (ROABPs), 2) Strict interval branching programs, 3) Sum of read once formulas with restricted ordering. We obtain parameterized lower bounds (i.e., n^Ω(t(k)) lower bound for some function t of k ) on the size of the above models computing a multilinear polynomial that can be computed by a depth four circuit of size g (k)n⁰⁽¹⁾ for some computable function g. Further, we obtain a parameterized separation between ROABPs and read-2 ABPs. This is obtained by constructing a degree k polynomial that can be computed by a read-2 ABP of small size such that the rank of the partial derivative matrix under any partition of the variables is large.

Słowa kluczowe

EN

circuit complexity; multilinear algebra; polynomials; computable functions; reading; size

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 177, nr 1
• Strony: 69--93
• Opis fizyczny: Bibliogr. 28 poz., rys.

Twórcy

autor

Ghosal Purnata

• Indian Institute of Technology, Madras, Chennai 600036, India

autor

Raghavendra Rao B. V.

• Indian Institute of Technology, Madras, Chennai 600036, India

Bibliografia

• [1] Valiant LG. The Complexity of Computing the Permanent. Theor. Comput. Sci., 1979. 8:189-201. doi:10.1016/0304-3975(79)90044-6.
• [2] Saptharishi R, Chillara S, Kumar M. A survey of lower bounds in arithmetic circuit complexity. Technical report, 2016. URL https://github.com/dasarpmar/lowerbounds-survey/releases.
• [3] Shpilka A, Yehudayoff A. Arithmetic Circuits: A Survey of Recent Results and Open Questions. Foundations and Trends in Theoretical Computer Science, 2010. 5(3-4):207-388. doi:10.1561/0400000039.
• [4] Baur W, Strassen V. The Complexity of Partial Derivatives. Theor. Comput. Sci., 1983. 22:317-330. doi:10.1016/0304-3975(83)90110-X.
• [5] Grochow JA, Mulmuley KD, Qiao Y. Boundaries of VP and VNP. In: Chatzigiannakis I, Mitzenmacher M, Rabani Y, Sangiorgi D (eds.), 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016 pp. 34:1-34:14. doi:10.4230/LIPIcs.ICALP.2016.34.
• [6] Downey RG, Fellows MR. Parameterized Complexity. Monographs in Computer Science. Springer, 1999. ISBN 978-1-4612-6798-0. doi:10.1007/978-1-4612-0515-9.
• [7] Engels C. Why are certain polynomials hard?: A look at non-commutative, parameterized and homomorphism polynomials. Ph.D. thesis, Saarland University, 2016. URL https://nbn-resolving.org/urn:nbn:de:bsz:291-scidok-64387.
• [8] Müller M. Parameterized Randomization. Ph.D. thesis, Albert-Ludwigs-Universität Freiburg im Breisgau, 2008. URL https://d-nb.info/993356915/34.
• [9] Kabanets V, Impagliazzo R. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. Comput. Complex., 2004. 13(1-2):1-46. doi:10.1007/s00037-004-0182-6.
• [10] Björklund A. Exact Covers via Determinants. In: Marion J, Schwentick T (eds.), 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France, volume 5 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010 pp. 95-106. doi:10.4230/LIPIcs.STACS.2010.2447.
• [11] Amini O, Fomin FV, Saurabh S. Counting Subgraphs via Homomorphisms. SIAM J. Discrete Math., 2012. 26(2):695-717. doi:10.1137/100789403.
• [12] Fomin FV, Lokshtanov D, Raman V, Saurabh S, Rao BVR. Faster algorithms for finding and counting subgraphs. J. Comput. Syst. Sci., 2012. 78(3):698-706. doi:10.1016/j.jcss.2011.10.001.
• [13] Björklund A, Husfeldt T, Taslaman N. Shortest cycle through specified elements. In: Rabani Y (ed.), Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012. SIAM, 2012 pp. 1747-1753. doi:10.1137/1.9781611973099.139.
• [14] Gupta A, Kamath P, Kayal N, Saptharishi R. Arithmetic Circuits: A Chasm at Depth Three. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA. IEEE Computer Society, 2013 pp. 578-587. doi:10.1109/FOCS.2013.68.
• [15] Fournier H, Limaye N, Malod G, Srinivasan S. Lower bounds for depth 4 formulas computing iterated matrix multiplication. In: Shmoys DB (ed.), Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. ACM, 2014 pp. 128-135. doi:10.1145/2591796.2591824.
• [16] Kumar M, Saraf S. The Limits of Depth Reduction for Arithmetic Formulas: It’s All About the Top Fan-In. SIAM J. Comput., 2015. 44(6):1601-1625. doi:10.1137/140999220.
• [17] Raz R. Multi-linear formulas for permanent and determinant are of super-polynomial size. J. ACM, 2009. 56(2):8:1-8:17. doi:10.1145/1502793.1502797.
• [18] Raz R. Separation of Multilinear Circuit and Formula Size. Theory of Computing, 2006. 2(6):121-135. doi:10.4086/toc.2006.v002a006.
• [19] Raz R, Yehudayoff A. Balancing Syntactically Multilinear Arithmetic Circuits. Comput. Complex., 2008. 17(4):515-535. doi:10.1007/s00037-008-0254-0.
• [20] Chillara S, Engels C, Limaye N, Srinivasan S. A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits. In: Thorup M (ed.), 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018. IEEE Computer Society, 2018 pp. 934-945. doi:10.1109/FOCS.2018.00092.
• [21] Kayal N, Nair V, Saha C. Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth Three Circuits. In: Ollinger N, Vollmer H (eds.), 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016 pp. 46:1-46:15. doi:10.4230/LIPIcs.STACS.2016.46.
• [22] Chen Z, Fu B. Approximating multilinear monomial coefficients and maximum multilinear monomials in multivariate polynomials. J. Comb. Optim., 2013. 25(2):234-254. doi:10.1007/s10878-012-9496-5.
• [23] Chen Z, Fu B, Liu Y, Schweller RT. On testing monomials in multivariate polynomials. Theor. Comput. Sci., 2013. 497:39-54. doi:10.1016/j.tcs.2012.03.038.
• [24] Chauhan A, Rao BVR. Parameterized Analogues of Probabilistic Computation. In: Ganguly S, Krishnamurti R (eds.), Algorithms and Discrete Applied Mathematics - First International Conference, CALDAM 2015, Kanpur, India, February 8-10, 2015. Proceedings, volume 8959 of Lecture Notes in Computer Science. Springer, 2015 pp. 181-192. doi:10.1007/978-3-319-14974-5_18.
• [25] Ghosal P, Prakash O, Rao BVR. On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction. In: Cao Y, Chen J (eds.), Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings, volume 10392 of Lecture Notes in Computer Science. Springer, 2017 pp. 250-261. doi:10.1007/978-3-319-62389-4_21.
• [26] Arvind V, Raja S. Some Lower Bound Results for Set-Multilinear Arithmetic Computations. Chicago J. Theor. Comput. Sci., 2016. 2016. URL http://cjtcs.cs.uchicago.edu/articles/2016/6/contents.html.
• [27] Nisan N. Lower Bounds for Non-Commutative Computation (Extended Abstract). In: Koutsougeras C, Vitter JS (eds.), Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA. ACM, 1991 pp. 410-418. doi:10.1145/103418.103462.
• [28] Hoory S, Linial N, Wigderson A. Expander graphs and their applications. Bulletin of the American Mathematical Society, 2006. 43(4):439-561. doi:10.1090/S0273-0979-06-01126-8.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).