2019/02/19 by Kumar, Mrinal, Oliveira, Rafael, Saptharishi, Ramprasad
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1902.07063
We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a depth-4 syntactically multilinear (ΣΠΣΠ) circuit of size at most exp(O(√(nlog n))). For degree d = ω(n/log n), this improves upon the upper bound of exp(O(√(d)log n)) obtained by Tavenas~\citeT15 for general circuits, and is known to be asymptotically optimal in the exponent when d < nε for a small enough constant ε. Our upper bound matches the lower bound of exp(Ω(√(nlog n))) proved by Raz and Yehudayoff~\citeRY09, and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree. More generally, we show that an n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear circuit of product-depth Δ of size at most exp(O(Δ⋅ (n/log n)1/Δ ⋅ log n)). It follows from the lower bounds of Raz and Yehudayoff (CC 2009) that in general, for constant Δ, the exponent in this upper bound is tight and cannot be improved to o((n/log n)1/Δ⋅ log n).