Improved bounds for reduction to depth 4 and depth 3

Koiran showed that if an n-variate polynomial f(n) of degree d (with d = n(O(1))) is computed by a circuit of size s, then it is also computed by a homogeneous circuit of depth four and of size 2(O(root dlog(n) log(s))). Using this result, Gupta, Kamath, Kayal and Saptharishi found an upper bound for the size of a depth three circuit computing f(n). We improve here Koiran's bound. Indeed, we transform an arithmetic circuit into a depth four circuit of size 2((O(root dlog(ds) log(n)))). Then, mimicking the proof in[2], it also implies a 2((O(root dlog(ds) log(n)))) upper bound for depth three circuits. This new bound is almost optimal since a 2(Omega(root d)) lower bound is known for the size of homogeneous depth four circuits such that gates at the bottom have fan-in at most root d. Finally, we show that this last lower bound also holds if the fan-in is at least root d. (C) 2014 Elsevier Inc. All rights reserved.