Hugues Randriambololona

  1. Bilinear complexity of algebras and the Chudnovsky-Chudnovsky interpolation method.

    Authors: Hugues Randriambololona
    Subjects: Computational Complexity
    Abstract

    We give a new generalization of the Chudnovsky-Chudnovsky method that
    provides upper bounds on the bilinear complexity of multiplication in
    monogenous algebras over finite fields through interpolation on algebraic
    curves. Two key features of our method is that we allow asymmetric
    interpolation, as well as interpolation at arbitrary closed subschemes. This
    allows us to fix errors in, improve, and generalize, previous works of
    Shparlinski-Tsfasman-Vladut, Ballet, and Cenk-\"Ozbudak.

Syndicate content