Intersection theory for lower bounds of algebraic branching programs

par Fulvio Gesmundo

jeudi 14 déc. 2023, 10:30 → 12:30 Europe/Paris

Algebraic branching programs (ABP) define one of the algebraic versions of the class of problems which can be solved in polynomial time. They are characterized by expressing a polynomial as the trace of a product of matrices of linear forms. We will see that polynomials admitting a small algebraic branching program present highly non-generic properties from an intersection theoretic point of view. This allows us to determine lower bounds on the ABP complexity, based on certain Noether-Lefschetz type conditions on the hypersurface defined by a polynomial. This is joint work with Ghosal, Ikenmeyer and Lysikov.