Quasi-polynomial Hitting-set for Set-depth-Delta Formulas

Manindra Agrawal, Chandan Saha, Nitin Saxena

We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition (X_1,...,X_d) of the variable indices [n] that the top product layer respects, i.e. C(x) = \sum_{i=1}^…