2023/02/14 by Hervé Fournier, Nutan Limaye, Fournier, Hervé +7
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Polynomial and algebraic computation
paper · pdf · doi:10.48550/arxiv.2302.06984
openalex publication_date 2023/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Classical results of Brent, Kuck and Maruyama (IEEE Trans. Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth O(log s) with only a polynomial blow-up in size. In this paper, we consider a fine-grained version of this result depending on the degree of the polynomial computed by the algebraic formula. Given a homogeneous algebraic formula of size s computing a polynomial P of degree d, we show that P can also be computed by an (unbounded fan-in) algebraic formula of depth O(log d) and size poly(s). Our proof shows that this result also holds in the highly restricted setting of monotone, non-commutative algebraic formulas. This improves on previous results in the regime when d is small (i.e., d<