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 have indicated a strategy 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. In this talk we will discuss the feasibility of the above strategy.
Homogeneous formula lower bounds. We will show lower bounds against ‘weighted’ homogeneous formulas of arbitrary depth. This is the first such lower bound for arbitrary depth formulas. This gives a strong indication that lower bounds against homogeneous formulas may be within reach.
Efficient homogenization. We show that any formula F for a homogeneous polynomial of degree d can be homogenized 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))).
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.
The talk is based on a joint work with Hervé Fournier, Srikanth Srinivasan, and Sébastien Tavenas.
