Speaker: |
Prof. Nutan Limaye (IT University of Copenhagen) |

Organiser: |
Ramprasad Saptharishi |

Date: |
Friday, 5 Jan 2024, 14:30 to 15:30 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

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.