Evènement pour le groupe Séminaire du LaBRI

Date 2012-03-15  14:00-15:00
TitrePower circuits and arithmetic for highly compressed integers 
RésuméPower circuits represent integers using directed acyclic graphs having edge and node labels from {-1,0,+1}. It generalizes the ``compact representation" of integers as sums over b_k 2^k where the b_k are not bits, but values in {-1,0,+1}. Power circuits of linear size O(n) may represent numbers involving tower values t(n) where t(0) = 1 and t(n) = 2^{t(n)}. Thus, the compression rate on some huge integers is extremely high. The data structure has been introduced by Myasnikov, Ushakov and Won in order to show that the word problem in the famous one-relator Baumslag group (a.k.a. Baumslag-Gersten group) can be solved in polynomial time. In my lecture, I report on a joint work with Laun and Ushakov which was presented this year at the STACS conference in Paris. I show that certain arithmetical operations can be performed efficiently, and I present an efficient reduction algorithm which is needed to compare values encoded in power circuits. Using these techniques we were able to improve the time bound for solving the word problem in the Baumslag group from O(n7) to cubic time, which we believe to be optimal. We also showed that the word problem in the Higman group H_4 can be solved in polynomial time. The focus of the talk is however more on power circuits than on the applications in algorithmic group theory.  
LieuAmphi du LaBRI 
OrateurVolker Diekert 
Url(FMI, Universität Stuttgart, Germany) 

Aucun document lié à cet événement.

Retour à l'index