Solving the conjugacy decision problem via machine learning

DOI10.1080/10586458.2018.1434704MaRDI QIDQ4960480zbMATH OpenOpenAlexFDO

Authors Jonathan Gryak, Robert Haralick, Delaram Kahrobaei

Publication date 16 April 2020

Published in Experimental Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1705.10417

zbMATH Keywords

conjugacygroup theorymachine learningnon-commutative cryptographypolycyclic group

Mathematics Subject Classification ID

Computational methods for problems pertaining to group theory (20-08) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this paper, we seek to extend these techniques to finitely presented non-free groups, with a particular emphasis on polycyclic and metabelian groups that are of interest to non-commutative cryptography. As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The accuracies of classifiers created using decision trees, random forests, and N-tuple neural network models are evaluated for several non-free groups. The very high accuracy of these classifiers suggests an underlying mathematical relationship with respect to conjugacy in the tested groups.

Recommendations

• scientific article; zbMATH DE number 2144700
• Artificial Intelligence and Symbolic Computation
• The status of polycyclic group-based cryptography: a survey and open problems
• scientific article; zbMATH DE number 5982274
• Decision and search in non-abelian Cramer-Shoup public key cryptosystem

Cites work

• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Generic-case complexity, decision problems in group theory, and random walks.
• Growth of finitely generated solvable groups
• Growth of finitely generated solvable groups and curvature of Riemannian manifolds
• scientific article; zbMATH DE number 5982274 (Why is no real title available?)
• scientific article; zbMATH DE number 2133330 (Why is no real title available?)
• scientific article; zbMATH DE number 2144700 (Why is no real title available?)
• scientific article; zbMATH DE number 3299786 (Why is no real title available?)
• Random forests
• Randomness and complexity in matrix groups
• Recursive unsolvability of a problem of Thue
• Scikit-learn: machine learning in Python
• The conjugacy problem in the Grigorchuk group is polynomial time decidable.
• THE LINEARITY OF THE CONJUGACY PROBLEM IN WORD-HYPERBOLIC GROUPS
• The status of polycyclic group-based cryptography: a survey and open problems

Cited in

(6)

• Evolution of group-theoretic cryptology attacks using hyper-heuristics
• Machine-learning the Sato-Tate conjecture
• A Machine Learning Based Software Pipeline to Pick the Variable Ordering for Algorithms with Polynomial Inputs
• Investigation of metabelian platform groups for protocols based on (simultaneous) conjugacy search problem
• Eidolon: a post-quantum signature scheme based on k-colorability in the age of graph neural networks
• Totally positive matrices and the highest-order coefficients of the characteristic polynomial

Describes a project that uses

Uses Software

• GAP
• Scikit

This page was built for publication: Solving the conjugacy decision problem via machine learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4960480)