Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 22 Novembre 2016 à 10:15

On Matrix Powering and Related Problems

par Joël Ouaknine (Sarrebruck)

I will discuss the Matrix Powering Positivity Problem, PosMatPow: given an m×m square integer matrix M, a linear function f : Zm×mZ with integer coefficients, and a positive integer n (encoded in binary), determine whether f(Mn) ≥ 0. Using techniques from algebraic and analytic number theory, it turns out that for fixed dimension m at most 3, one can show that this problem is decidable in polynomial time (the complexity is open in higher dimensions). I will also present and discuss a number of related problems, including the Euclidean Travelling Salesman Problem, the Sum-of-Square-Roots Problem, and the Positivity Problem for Straight-Line Programs (PosSLP). This is joint work with James Worrell and Esther Galby.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30