Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

摘要

We show that any n -variate polynomial computable by a syntactically multilinear circuit of size pol y ( n ) can be computed by a depth- 4 syntactically multilinear ( ) circuit of size at most exp O n log n . For degree d = ( n log n ) , this improves upon the upper bound of exp O ( d log n ) obtained by Tavenas (MFCS 2015) 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 n log n proved by Raz and Yehudayoff (CC 2009), 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 pol y ( 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 .