On the power of border of depth-3 arithmetic circuits

DOI10.1145/3371506MaRDI QIDQ5053057zbMATH OpenOpenAlexFDO

Authors Mrinal Kumar

Publication date 5 December 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

algebraic complexityborder complexitydepth reductionslower bounds

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We show that over the field of complex numbers, emph{every} homogeneous polynomial of degree $d$ can be approximated (in the border complexity sense) by a depth-$3$ arithmetic circuit of top fan-in at most $d+1$. This is quite surprising since there exist homogeneous polynomials $P$ on $n$ variables of degree $2$, such that any depth-$3$ arithmetic circuit computing $P$ must have top fan-in at least $Omega(n)$. As an application, we get a new tradeoff between the top fan-in and formal degree in an approximate analog of the celebrated depth reduction result of Gupta, Kamath, Kayal and Saptharishi [GKKS13]. Formally, we show that if a degree $d$ homogeneous polynomial $P$ can be computed by an arithmetic circuit of size $s$, then for every $tleqd$, $P$ is in the border of a depth-$3$ circuit of top fan-in $s^{O(t)}$ and formal degree $s^{O(d/t)}$. To the best of our knowledge, the upper bound on the top fan-in in the original proof of [GKKS13] is always at least $s^{O(sqrtd)}$, regardless of the formal degree.

Recommendations

• Improved Bounds for Reduction to Depth 4 and Depth 3
• Improved bounds for reduction to depth 4 and depth 3
• Finer separations between shallow arithmetic circuits
• An almost cubic lower bound for depth three arithmetic circuits
• Depth-3 arithmetic circuits over fields of characteristic zero

Cited in

(7)

• On the closures of monotone algebraic classes and variants of the determinant
• On the closures of monotone algebraic classes and variants of the determinant
• Geometric complexity theory for product-plus-power
• On the power of border width-2 ABPs over fields of characteristic 2
• Fixed-parameter debordering of Waring rank
• Homogeneous algebraic complexity theory and algebraic formulas
• Structure and linear time recognition of 3-leaf powers

This page was built for publication: On the power of border of depth-3 arithmetic circuits

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