TR23-191 Authors: Hervé Fournier, Nutan Limaye, Srikanth Srinivasan, Sébastien Tavenas

Publication: 3rd December 2023 11:07

Downloads: 284

Keywords:

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 is 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 $d^{O(\log s)}.$ We show that this can be improved superpolynomially over fields of characteristic $0$ as long as $d = s^{o(1)}.$ Such a result was previously only known when $d = (\log s)^{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 against 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(\sqrt{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.