On the Power of Border of Depth-3 Arithmetic Circuits

Abstract

We show that over the field of complex numbers, 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 2. 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 Ω ( 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 [7, 10]. Formally, we show that if a degree d homogeneous polynomial P can be computed by an arithmetic circuit of size s ≥ d , then for every t ≤ d , 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 Reference [7] is always at least s Ω (√d) , regardless of the formal degree.