On top fan-in vs formal degree for depth-3 arithmetic circuits
share
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 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 Ω(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 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 [GKKS13] is always at least s^O(√(d)), regardless of the formal degree.
READ FULL TEXT