Solving the Conjugacy Decision Problem via Machine Learning

References

• [Bledsoe and Browning 59] W. W. Bledsoe and I. Browning. “Pattern Recognition and Reading by Machine.” Papers Presented at the Eastern Joint IRE-AIEE-ACM Computer Conference, pp. 225–232. ACM, December 1–3, 1959.
   Google Scholar
• [Breiman 01] L. Breiman. “Random Forests.” Mach. Learn. 45:1 (2001), 5–32.
   Web of Science ®Google Scholar
• [Dehn 11] M. Dehn. “Über Unendliche Diskontinuierliche Gruppen.” Math. Annal. 71:1 (1911), 116–144.
   Google Scholar
• [Eick et al. 13] B. Eick, W. Nickel, and M. Horn. “Polycyclic, Computation with Polycyclic Groups, Version 2.11.” Available online: http://www.icm.tu-bs.de/ag_algebra/software/polycyclic/, Mar 2013. Refereed GAP package.
   Google Scholar
• [Epstein and Holt 06] D. Epstein and D. Holt. “The Linearity of the Conjugacy Problem in Word-Hyperbolic Groups.” Int. J. Algebra Comput. 16:02 (2006), 287–305.
   Google Scholar
• [GAP 16] GAP – Groups. “Algorithms, and Programming, Version 4.8.5.” Available online http://www.gap-system.org, 2016.
   Google Scholar
• [Garber et al. 15] D. Garber, D. Kahrobaei, and H. T. Lam. “Length-Based Attack for Polycyclic Groups.” J. Math. Cryptol. De Gruyter. 9:1 (2015), 33–44.
   Web of Science ®Google Scholar
• [Gryak and Kahrobaei 16] J. Gryak and D. Kahrobaei. “The Status of Polycyclic Group-Based Cryptography: A Survey and Open Problems.” Groups Complex. Cryptol. 8:2 (2016), 171–186.
   Google Scholar
• [Gryak et al. 16] J. Gryak, D. Kahrobaei, and C. Martinez-Perez. “On the Conjugacy Problem in Certain Metabelian Groups.” Glasgow Mathematical Journal: Cambridge University Press arXiv preprint arXiv:1610.06503, 2016.
   Google Scholar
• [Haralick 15] R. Haralick. N-Tuple Method. University Lecture, 2015.
   Google Scholar
• [Haralick et al. 04] R. Haralick, A. D. Miasnikov, and A. G. Myasnikov. “Pattern Recognition Approaches to Solving Combinatorial Problems in Free Groups.” Computational and Experimental Group Theory: AMS-ASL Joint Special Session, Interactions Between Logic, Group Theory, and Computer Science, Vol. 349, pp. 197–213, Baltimore, Maryland, January 15–16, 2003, 2004.
   Google Scholar
• [Holt et al. 05] D. F. Holt, B. Eick, and E. A. O’Brien. Handbook of Computational Group Theory. Discrete Mathematics and its Applications (Boca Raton). Boca Raton, FL: Chapman & Hall/CRC, 2005.
   Google Scholar
• [Kapovich et al. 03] I. Kapovich, A. G. Myasnikov, P. Schupp, and V. Shpilrain. “Generic-Case Complexity, Decision Problems in Group Theory, and Random Walks.” J. Algebra 264:2 (2003), 665–694.
   Web of Science ®Google Scholar
• [Knuth and Bendix 70] D. E. Knuth and P. B. Bendix. “Simple Word Problems in Universal Algebras.” Comput. Problem. Abstract Algebra (1970), 263–297. Available online https://doi.org/10.1016/B978-0-08-012975-4.50028-X
   Google Scholar
• [Kołcz and Allinson 94] A. Kołcz and N. M. Allinson. “Application of the CMAC Input Encoding Scheme in the N-Tuple Approximation Network.” IEE Proc.-Comput. Digital Techn. 141:3 (1994), 177–183.
   Google Scholar
• [Kołcz and Allinson 96] A. Kołcz and N. M. Allinson. “N-Tuple Regression Network.” Neural Network. 9:5 (1996), 855–869.
   PubMed Web of Science ®Google Scholar
• [Lysenok et al. 10] I. Lysenok, A. G. Myasnikov, and A. Ushakov. “The Conjugacy Problem in the Grigorchuk Group is Polynomial Time Decidable.” Groups, Geom. Dyn. 4:4 (2010), 813–833.
   Web of Science ®Google Scholar
• [Milnor 68] J. Milnor. “Growth of Finitely Generated Solvable Groups.” J. Differ. Geom. 2:4 (1968), 447–449.
   Google Scholar
• [Myasnikov et al. 11] A. G. Myasnikov, V. Shpilrain, A. Ushakov, and N. Mosina. Non-Commutative Cryptography and Complexity of Group-Theoretic Problems, Vol. 177. RI, USA: American Mathematical Society Providence, 2011.
   Google Scholar
• [Novikov 55] P. S. Novikov. “On the Algorithmic Unsolvability of the Word Problem in Group Theory.” Trudy Matem. Inst. imeni V.A. Steklova 44 (1955), 3–143.
   Google Scholar
• [Pedregosa et al. 11] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. “Scikit-learn: Machine Learning in Python.” J. Mach. Learn. Res. 12 (2011), 2825–2830.
   Web of Science ®Google Scholar
• [Post 47] E. L. Post. “Recursive Unsolvability of a Problem of Thue.” J. Symbolic Logic 12:1 (1947), 1–11.
   Google Scholar
• [Rohwer and Morciniec 98] R. Rohwer and M. Morciniec. “The Theoretical and Experimental Status of the n-Tuple Classifier.” Neural Network 11:1 (1998), 1–14.
   PubMed Web of Science ®Google Scholar
• [Shpilrain 17] V. Shpilrain. “Randomness and Complexity in Matrix Groups.” Available online http://www.sci.ccny.cuny.edu/shpil/matrix_complex.pdf, 2017.
   Google Scholar
• [Tattersall et al. 91] G. D. Tattersall, S. Foster, and Robert D. Johnston. “Single-Layer Lookup Perceptrons.” In IEE Proceedings F-Radar and Signal Processing, Vol. 138, pp. 46–54. IET, 1991.
   Google Scholar
• [Weiß 16] A. Weiß. “A Logspace Solution to the Word and Conjugacy Problem of Generalized Baumslag-Solitar Groups.” Algebra Comput. Sci. 677 (2016), 185.
   Google Scholar
• [Wolf 68] J. A. Wolf. “Growth of Finitely Generated Solvable Groups and Curvature of Riemannian Manifolds.” J. Different. Geom. 2:4 (1968), 421–446.
   Google Scholar