Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 21 janvier 2014 à 12h00 en B107, Gleb Koshevoy nous parlera de : Cluster algebras and subtraction-free computing

Résumé : Using cluster transformations we design subtraction-free algorithms for computing Schur functions and their skew, double and supersymemtric analogues, for generating spanning trees and arborescences polynomials. The latter provides an exponential complexity gap between circuits admitting arithmetic operations +, x, / versus +, x. In addition, we establish an exponential complexity gap between circuits admitting +, -, x, / versus +, x, /. Together with V. Strassen's result on "Vermeidung von Divisionen" this closes a long-standing problem on comparative complexity power between all possible subsets of operations +, -, x, /. (joint work with S. Fomin and D. Grigoriev)

Dernière modification : Monday 27 May 2024 Valid HTML 4.01! Valid CSS! Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr