a computational proof of complexity of some restricted counting problems

South Central University

Application of dynamical Lie algebraic method to atom-diatomic molecule scattering

The dynamical Lie algebraic approach developed by Alhassid and Levine combined with intermediate picture is applied to the study of translational-vibrational energy transfer in the collinear collision between an atom and an anharmonic oscillator. We find that the presence of the anharmonic terms indeed has an effect on the vibrational probabilities of the oscillator. The computed probabilities are in good agreement with those obtained using exact quantum method. It is shown that the approach of dynamical Lie algebra combining with intermediate picture is reasonable in the treating of atom-anharmonic oscillator scattering.

On the Stable Paths Problem and a Restricted Variant

Interdomain routing on the Internet is performed using route preference policies specified independently, and arbitrarily by each Autonomous System in the network. These policies are used in the border gateway protocol (BGP) by each AS when selecting next-hop choices for routes to each destination. Conflicts between policies used by different ASs can lead to routing instabilities that, potentially, cannot be resolved no matter how long BGP is run. The Stable Paths Problem (SPP) is an abstract graph theoretic model of the problem of selecting nexthop routes for a destination. A stable solution to the problem is a set of next-hop choices, one for each AS, that is compatible with the policies of each AS. In a stable solution each AS has selected its best next-hop given that the next-hop choices of all neighbors are fixed. BGP can be viewed as a distributed algorithm for solving SPP. In this report we consider the stable paths problem, as well as a family of restricted variants of the stable paths problem, which we call F stable paths problems. We show that two very simple variants of the stable paths problem are also NP-complete. In addition we show that for networks with a DAG topology, there is an efficient centralized algorithm to solve the stable paths problem, and that BGP always efficiently converges to a stable solution on such networks.

The abelianization of the Johnson kernel

We prove that the first complex homology of the Johnson subgroup of the Torelli group Tg is a non-trivial, unipotent Tg-module for all g ≥ 4 and give an explicit presentation of it as a Sym H 1(Tg,C)-module when g ≥ 6. We do this by proving that, for a finitely generated group G satisfying an assumption close to formality, the triviality of the restricted characteristic variety implies that the first homology of its Johnson kernel is a nilpotent module over the corresponding Laurent polynomial ring, isomorphic to the infinitesimal Alexander invariant of the associated graded Lie algebra of G. In this setup, we also obtain a precise nilpotence test. © European Mathematical Society 2014.

SK1-like functors for division algebras

We investigate the group valued functor G(D) = D*/F*D' where D is a division algebra with center F and D' the commutator subgroup of D*. We show that G has the most important functorial properties of the reduced Whitehead group SK1. We then establish a fundamental connection between this group, its residue version, and relative value group when D is a Henselian division algebra. The structure of G(D) turns out to carry significant information about the arithmetic of D. Along these lines, we employ G(D) to compute the group SK1(D). As an application, we obtain theorems of reduced K-theory which require heavy machinery, as simple examples of our method.