Given a loop on a surface, its homotopy class can be specified as a word consisting of letters representing the homotopy group generators. One of the interesting problems is how to compute the shortest word for a given loop. This is an NP-hard problem in general. However, for a closed surface that allows a hyperbolic metric and is equipped with a canonical set of fundamental group generators, the shortest word problem can be reduced to finding the shortest loop that is homotopic to the given loop, which can be solved efficiently. In this paper, we propose an efficient algorithm to compute the shortest words for loops given on triangulated surface meshes. The design of this algorithm is inspired and guided by the work of Dehn and BirmanSeries. In support of the shortest word algorithm, we also propose efficient algorithms to compute shortest paths and shortest loops under hyperbolic metrics using a novel

No abstract uploaded!

In this paper, we present a new algorithm, such that, for the small integer solution (SIS) problem, if the solution is bounded ( by an integer \beta in l_\infty norm, which we call a bounded SIS (BSIS) problem, {\it and if the difference between the row dimension n and the column dimension m of the corresponding matrix is relatively small with respect the row dimension m}, we can solve it easily with a complexity of polynomial in m.

Using the complex coloring method, we present the graphs of the quantum dilogarithm function Gb(z) and visualize its analytic and asymptotic behaviours. In particular we demonstrate the limiting process when the modified Gb(z)→Γ(z) as b→0. We also survey the relations of Gb(z) with different variants of the quantum dilogarithm function.

In all the odd dimensions which allow Majorana spinors, we consider a gravitational Lagrangian possessing local Poincare invariance and given by the dimensional continuation of the Euler density in one dimension less. We show that the local supersymmetric extension of this Lagrangian requires the algebra to be the maximal extension of the N=1 super-Poincare algebra. By maximal, we mean that in the right hand side of the anticommutator of the Majorana super charge appear all the possible central charges. The resulting action defines a Chern-Simons gauge theory for the maximal extension of the super-Poincare algebra. In these dimensions, we address the same problem for the AdS invariant gravity and we derive its supersymmetric extension for the minimal super-AdS algebra. The connection between both models is realized at the algebraic level through an expansion of their corresponding Lie super algebras. Within a procedure consistent with the expansion of the algebras, the local supersymmetric extension of the Poincare invariant gravity Lagrangian is derived from the super AdS one.