Lower Bounds for Noncommutative Circuits with Low Syntactic Degree

Proving lower bounds on the size of noncommutative arithmetic circuits is an important problem in arithmetic circuit complexity. For explicit n variate polynomials of degree Θ (n), the best known general bound is Ω (n log n) Strassen, 1973; Walter Baur and Volker Strassen, 1983. Recent work of Chatterjee and Hrubeš Chatterjee and Hrubeš, 2023 has provided stronger (Ω (n²) ) bounds for the restricted class of homogeneous circuits. The present paper extends these results to a broader class of circuits by using syntactic degree as a complexity measure. The syntactic degree of a circuit is a well known parameter which measures the extent to which high degree computation is used in the circuit. A homogeneous circuit computing a degree d polynomial can be assumed, without loss of generality, to have syntactic degree exactly equal to d Fournier et al. , 2024. We generalize this by considering circuits that are not necessarily homogeneous but have low syntactic degree. Specifically, for an explicit n variate, degree n polynomial f we show that any circuit with syntactic degree O (n) computing f must have size Ω (n^1+c) for some constant c > 0. We also show that any circuit with syntactic degree o (nlog n) computing the same f must have size ω (nlog n). We further analyze the circuit size required to compute f based on the number of distinct syntactic degrees appearing in the circuit. Our analysis yields an ω (nlog n) size lower bound for all but a narrow parameter regime where an improved bound is not obtained. Finally, we observe that low syntactic degree circuits are more powerful than homogeneous circuits in a fine grained sense: there exists an n variate, degree Θ (n) polynomial that has a circuit of size O (nlog ²n) and syntactic degree O (n) but any homogeneous circuit computing it requires size Ω (n²).