Improved bounds for reduction to depth 4 and depth 3

Koiran showed that if an n  -variate polynomial fnfn of degree d   (with d=nO(1)d=nO(1)) is computed by a circuit of size s  , then it is also computed by a homogeneous circuit of depth four and of size 2O(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 fnfn.We improve here Koiran's bound. Indeed, we transform an arithmetic circuit into a depth four circuit of size 2(O(dlog⁡(ds)log⁡(n))). Then, mimicking the proof in [2], it also implies a 2(O(dlog⁡(ds)log⁡(n))) upper bound for depth three circuits.This new bound is almost optimal since a 2Ω(d) lower bound is known for the size of homogeneous depth four circuits such that gates at the bottom have fan-in at most d. Finally, we show that this last lower bound also holds if the fan-in is at least d.