Low-depth arithmetic circuit lower bounds via shifted partials - Amireddy, Prashanth; Garg, Ankit; Kayal, Neeraj; Saha, Chandan; Thankey, Bhargav (Electronic Colloquium on Computational Complexity, 2022, 2022)
We prove superpolynomial lower bounds for low-depth arithmetic circuits using the shifted partials measure [GKKS14,Kay12] and the affine projections of partials measure [GKS20,KNS20]. The recent breakthrough work of Limaye, Srinivasan and Tavenas [LST21] proved these lower bounds by proving lower bounds for low-depth set-multilinear circuits. An interesting aspect of our proof is that it does not require conversion of a circuit to a set-multilinear circuit, nor does it involve random restrictions. We are able to upper bound the measures for homogeneous formulas directly, without going via set-multilinearity. Our lower bounds hold for the iterated matrix multiplication as well as the Nisan-Wigderson design polynomials. We also define a subclass of homogeneous formulas which we call unique parse tree (UPT) formulas, and prove superpolynomial lower bounds for these. This generalizes the superpolynomial lower bounds for regular formulas [KSS14,FLMS15].