On the Power of Homogeneous Algebraic Formulas

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking this question: show that we can convert a general algebraic formula to a homogeneous algebraic formula with moderate blow-up in size, and prove strong lower bounds against the latter model. Here, a homogeneous algebraic formula F for a polynomial P is a formula in which all subformulas compute homogeneous polynomials. In particular, if P is homogeneous of degree d, F does not contain subformulas that compute polynomials of degree greater than d. We investigate the feasibility of the above strategy and prove a number of positive and negative results in this direction.

Lower bounds against weighted homogeneous formulas: We show the first lower bounds against homogeneous formulas of any depth in the weighted setting. Here, each variable has a given weight and the weight of a monomial is the sum of weights of the variables in it. This result builds on a lower bound of Hrubeš and Yehudayoff (Computational Complexity 2011) against homogeneous multilinear formulas. This result is strong indication that lower bounds against homogeneous formulas are within reach. Improved (quasi-)homogenization for formulas: A simple folklore argument shows that any formula F for a homogeneous polynomial of degree d can be homogenized with a size blow-up of dO(logs). We show that this can be improved superpolynomially over fields of characteristic 0 as long as d = so(1). Such a result was previously only known when d = (logs)1+o(1) (Raz (J. ACM 2013)). Further, we show how to get rid of the condition on d at the expense of getting a quasi-homogenization result: this means that subformulas can compute polynomials of degree up to poly(d). Lower bounds for non-commutative homogenization: A recent result of Dutta, Gesmundo, Ikenmeyer, Jindal and Lysikov (2022) implies that to homogenize algebraic formulas of any depth, it suffices to homogenize non-commutative algebraic formulas of depth just 3. We are able to show strong lower bounds for such homogenization, suggesting barriers for this approach. No Girard-Newton identities for positive characteristic: In characteristic 0, it is known how to homogenize constant-depth algebraic formulas with a size blow-up of exp(O(√d)) using the Girard-Newton identities. Finding analogues of these identities in positive characteristic would allow us, paradoxically, to show lower bounds for constant-depth formulas over such fields. We rule out a strong generalization of Girard-Newton identities in the setting of positive characteristic, suggesting that a different approach is required.