Efficient Average-Case Algorithms for the Modular Group

The modular group occupies a central position in many branches of mathematical sciences. In this paper we give average polynomial-time algorithms for the unbounded and bounded membership problems for finitely generated subgroups of the modular group. The latter result affirms a conjecture of Y. Gurevich (1990). >

Authors

• Jin-Yi Cai
• Wolfgang H. J. Fuchs
• Dexter Kozen
• Zicheng Liu 0001

Keywords

• Elliptic curves
• Polynomials
• Algorithm design and analysis
• Character generation
• Geometry
• Lattices
• Optical design
• Linear programming
• Computer applications
• Efficient Algorithm
• Modular Group
• Conjecture
• Polynomial-time Algorithm
• Directed Graph
• Normal Form
• Elliptic Curve
• Finite Subset
• Induction Hypothesis
• Sequential Reduction
• Matrix Integrity
• Automorphism Group
• Group Of Transformations
• Path Computation
• Hyperbolic Geometry