Depth-4 lower bounds, determinantal complexity: a unified approach

DOI10.4230/LIPICS.STACS.2014.239zbMATH Open1359.68123arXiv1308.1640OpenAlexW2964011532MaRDI QIDQ2965487FDOQ2965487

Authors: Suryajith Chillara, Partha Mukhopadhyay 

Publication date: 3 March 2017

Abstract: Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 circuit of size 2^{O(sqrt{n}log n)}. So to prove VP not equal to VNP, it is sufficient to show that an explicit polynomial in VNP of degree n requires 2^{omega(sqrt{n}log n)} size depth-4 circuits. Soon after Tavenas's result, for two different explicit polynomials, depth-4 circuit size lower bounds of 2^{Omega(sqrt{n}log n)} have been proved Kayal et al. and Fournier et al. In particular, using combinatorial design Kayal et al. construct an explicit polynomial in VNP that requires depth-4 circuits of size 2^{Omega(sqrt{n}log n)} and Fournier et al. show that iterated matrix multiplication polynomial (which is in VP) also requires 2^{Omega(sqrt{n}log n)} size depth-4 circuits. In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies the property would achieve similar circuit size lower bound for depth-4 circuits. In particular, it does not matter whether f is in VP or in VNP. As a result, we get a very simple unified lower bound analysis for the above mentioned polynomials. Another goal of this paper is to compare between our current knowledge of depth-4 circuit size lower bounds and determinantal complexity lower bounds. We prove the that the determinantal complexity of iterated matrix multiplication polynomial is Omega(dn) where d is the number of matrices and n is the dimension of the matrices. So for d=n, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth-4 circuit size and determinantal complexity. To the best of our knowledge, a Theta(n) bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for constant d>1 by Jansen.

Full work available at URL: https://arxiv.org/abs/1308.1640

Recommendations

• Depth-4 lower bounds, determinantal complexity: a unified approach
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Lower bounds for depth 4 formulas computing iterated matrix multiplication
• On the power of homogeneous depth 4 arithmetic circuits
• On the limits of depth reduction at depth 3 over small finite fields

zbMATH Keywords

arithmetic circuitsdeterminantal complexitydepth-4 lower bounds

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Determinants, permanents, traces, other special matrix functions (15A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (12)

• On the Symmetries of and Equivalence Test for Design Polynomials.
• A Selection of Lower Bounds for Arithmetic Circuits
• On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
• On the power of homogeneous depth 4 arithmetic circuits
• Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
• The computational power of depth five arithmetic circuits
• Lower bounds for the determinantal complexity of explicit low degree polynomials
• Depth-4 lower bounds, determinantal complexity: a unified approach
• The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
• On the limits of depth reduction at depth 3 over small finite fields
• Lower bounds for depth-4 formulas computing iterated matrix multiplication
• Improved Bounds for Reduction to Depth 4 and Depth 3

This page was built for publication: Depth-4 lower bounds, determinantal complexity: a unified approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2965487)