
Evènement pour le groupe Séminaire du LaBRI
Date  20120315 14:0015:00 
Titre  Power 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 onerelator Baumslag group (a.k.a. BaumslagGersten 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. 
Lieu  Amphi du LaBRI 
Orateur  Volker Diekert 
Url  (FMI, Universität Stuttgart, Germany) 
Aucun document lié à cet événement. RetourRetour à l'index
 