On top fan-in vs formal degree for depth-3 arithmetic circuits

摘要

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.