@article{TAVENAS20152,
    Abstract = {Koiran showed that if an n-variate polynomial fn of degree d (with 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 fn. 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.},
    Author = {Tavenas, S{\'e}bastien},
    File = {Improved bounds for reduction to depth 4 and depth 3 - 1-s2.0-S0890540114001138-main.pdf},
    ISSN = {0890-5401},
    Journal = {Information and Computation},
    Keywords = {Arithmetic circuit, Parallelization},
    Note = {MFCS 2013},
    Pages = {2-11},
    Title = {Improved bounds for reduction to depth 4 and depth 3},
    URL = {https://www.sciencedirect.com/science/article/pii/S0890540114001138},
    Volume = {240},
    Year = {2015},
    bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0890540114001138},
    bdsk-url-2 = {https://doi.org/10.1016/j.ic.2014.09.004},
    date-added = {2023-10-06 14:36:06 +0200},
    date-modified = {2023-10-06 14:36:06 +0200},
    doi = {10.1016/j.ic.2014.09.004}
}

@article{TAVENAS20152, Abstract = {Koiran showed that if an n-variate polynomial fn of degree d (with 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 fn. 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.}, Author = {Tavenas, S{\'e}bastien}, File = {Improved bounds for reduction to depth 4 and depth 3 - 1-s2.0-S0890540114001138-main.pdf}, ISSN = {0890-5401}, Journal = {Information and Computation}, Keywords = {Arithmetic circuit, Parallelization}, Note = {MFCS 2013}, Pages = {2-11}, Title = {Improved bounds for reduction to depth 4 and depth 3}, URL = {https://www.sciencedirect.com/science/article/pii/S0890540114001138}, Volume = {240}, Year = {2015}, bdsk-url-1 = {https://www.sciencedirect.com/science/article/pii/S0890540114001138}, bdsk-url-2 = {https://doi.org/10.1016/j.ic.2014.09.004}, date-added = {2023-10-06 14:36:06 +0200}, date-modified = {2023-10-06 14:36:06 +0200}, doi = {10.1016/j.ic.2014.09.004} }