• DocumentCode
    2653472
  • Title

    Algebras of Minimal Multiplicative Complexity

  • Author

    Bläser, Markus ; Chokaev, Bekhan

  • Author_Institution
    Dept. of Comput. Sci., Saarland Univ., Saarbrucken, Germany
  • fYear
    2012
  • fDate
    26-29 June 2012
  • Firstpage
    224
  • Lastpage
    234
  • Abstract
    We prove that an associative algebra A has minimal rank if and only if the Alder-Strassen bound is also tight for the multiplicative complexity of A, that is, the multiplicative complexity of A is 2 dim A - tA where tA denotes the number of maximal twosided ideals of A. This generalizes a result by E. Feig who proved this for division algebras. Furthermore, we show that if A is local or superbasic, then every optimal quadratic computation for A is almost bilinear.
  • Keywords
    algebra; computational complexity; Alder-Strassen bound; associative algebra; bilinear computation; division algebras; maximal two-sided ideals; minimal multiplicative complexity algebras; minimal rank; optimal quadratic computation; Complexity theory; Computer science; Educational institutions; Polynomials; Vectors; algebraic complexity theory; associative algebra; complexity of bilinear problems;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity (CCC), 2012 IEEE 27th Annual Conference on
  • Conference_Location
    Porto
  • ISSN
    1093-0159
  • Print_ISBN
    978-1-4673-1663-7
  • Type

    conf

  • DOI
    10.1109/CCC.2012.13
  • Filename
    6243398
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2653472