This talk will present recent advances in obtaining better lower bounds for algebraic formulas. We will discuss a parallelization technique that achieves logarithmic depth in the degree for small homogeneous formulas, which reduces the problem of obtaining lower bounds for general homogeneous formulas to that of small depth formulas. We will also explore how superpolynomial lower bounds can be obtained in the low-degree and low-depth regime by applying the partial derivative method to certain lopsided set-multilinear polynomials. These lower bounds will continue to be superpolynomial for formulas of depth at most O(log(log(d))). Finally, we will show that the best lower bound we can prove for set-multilinear formulas of product-depth D can be characterized in terms of the combinatorial properties of a specific multi-set W of size d, referred to as the “depth-D tree bias” of W.
This talk is based on joint work with Nutan Limaye, Srikanth Srinivasan, Hervé Fournier, and Guillaume Malod.
This video was produced by the University of Warwick as part of the 7th Workshop on Algebraic Complexity Theory (WACT) 2023.
