@article{amireddy2022low-depth,
author = {Amireddy, Prashanth and Garg, Ankit and Kayal, Neeraj and Saha, Chandan and Thankey, Bhargav},
title = {Low-depth arithmetic circuit lower bounds via shifted partials},
year = {2022},
month = {November},
abstract = {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].},
url = {http://approjects.co.za/?big=en-us/research/publication/low-depth-arithmetic-circuit-lower-bounds-via-shifted-partials/},
journal = {Electronic Colloquium on Computational Complexity, 2022},
}