Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this dissertation, we seek to extend these techniques to finitely presented non-free groups, in particular to 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.
In addition to testing these techniques on several well-known finitely presented groups, we introduce a new family of metabelian groups for which we analyze the computational complexity of the conjugacy search problem. We prove that for the family in general the time complexity of the conjugacy search problem is exponential, while for a subfamily the problem is polynomial. We also show that for some of these groups the conjugacy search problem is an instance of the discrete logarithm problem.
We also apply machine learning techniques to solving the conjugacy search problem. For each platform group we train a N-tuple regression network that can produce a candidate conjugator for a pair of conjugate elements. This candidate is then used as the initial state of a local search for a conjugator in the Cayley graph, in what we call regression-based conjugacy search (RBCS). RBCS can be applied to groups such as polycyclic groups for which other heuristic approaches, such as the length-based attack, are ineffective.
","abstract_html":"<p>Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this dissertation, we seek to extend these techniques to finitely presented non-free groups, in particular to polycyclic and metabelian groups that are of interest to non-commutative cryptography.</p> <p>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 <em>N</em>-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.</p> <p>In addition to testing these techniques on several well-known finitely presented groups, we introduce a new family of metabelian groups for which we analyze the computational complexity of the conjugacy search problem. We prove that for the family in general the time complexity of the conjugacy search problem is exponential, while for a subfamily the problem is polynomial. We also show that for some of these groups the conjugacy search problem is an instance of the discrete logarithm problem.</p> <p>We also apply machine learning techniques to solving the conjugacy search problem. For each platform group we train a <em>N</em>-tuple regression network that can produce a candidate conjugator for a pair of conjugate elements. This candidate is then used as the initial state of a local search for a conjugator in the Cayley graph, in what we call regression-based conjugacy search (RBCS). RBCS can be applied to groups such as polycyclic groups for which other heuristic approaches, such as the length-based attack, are ineffective.</p>","abstract_has_math":false,"creators":["Gryak, Jonathan"],"institution":"The Graduate School and University Center of The City University of New York","degree_name":"Doctor of Philosophy","degree_level":"Doctoral","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":["Delaram Kahrobaei"],"committee_chairs":[],"committee_members":["Benjamin Fine","Robert Haralick","Delaram Kahrobaei","Vladimir Shpilrain","Xiaowen Zhang"],"year":2017,"date_issued":"2017-06-02T07:00:00Z","date_published":"2017-06-02T07:00:00Z","updated_at":"2026-07-24T01:59:30Z","subjects":["Algebra","Artificial Intelligence and Robotics","Discrete Mathematics and Combinatorics","Theory and Algorithms","group theory","machine learning","non-commutative cryptography","conjugacy","polycyclic group"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://academicworks.cuny.edu/gc_etds/2045","outbound_label":"Repository record","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Delaram Kahrobaei"]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Benjamin Fine","Robert Haralick","Delaram Kahrobaei","Vladimir Shpilrain","Xiaowen Zhang"]},{"key":"dc:creator","label":"Author","values":["Gryak, Jonathan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.available","label":"Dc Date Available","values":["2019-06-02T07:00:00Z"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctoral"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Doctor of Philosophy"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["The Graduate School and University Center of The City University of New York"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Algebra","Artificial Intelligence and Robotics","Discrete Mathematics and Combinatorics","Theory and Algorithms","group theory","machine learning","non-commutative cryptography","conjugacy","polycyclic group"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://academicworks.cuny.edu/gc_etds/2045"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this dissertation, we seek to extend these techniques to finitely presented non-free groups, in particular to 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.
In addition to testing these techniques on several well-known finitely presented groups, we introduce a new family of metabelian groups for which we analyze the computational complexity of the conjugacy search problem. We prove that for the family in general the time complexity of the conjugacy search problem is exponential, while for a subfamily the problem is polynomial. We also show that for some of these groups the conjugacy search problem is an instance of the discrete logarithm problem.
We also apply machine learning techniques to solving the conjugacy search problem. For each platform group we train a N-tuple regression network that can produce a candidate conjugator for a pair of conjugate elements. This candidate is then used as the initial state of a local search for a conjugator in the Cayley graph, in what we call regression-based conjugacy search (RBCS). RBCS can be applied to groups such as polycyclic groups for which other heuristic approaches, such as the length-based attack, are ineffective.
"]},{"key":"dc:title","label":"Title","values":["Solving Algorithmic Problems in Finitely Presented Groups via Machine Learning"]}]}],"canonical_facts":{"dc:contributor.advisor":["Delaram Kahrobaei"],"dc:contributor.committeemember":["Benjamin Fine","Robert Haralick","Delaram Kahrobaei","Vladimir Shpilrain","Xiaowen Zhang"],"dc:creator":["Gryak, Jonathan"],"dc:date.available":["2019-06-02T07:00:00Z"],"dc:description.abstract":["Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this dissertation, we seek to extend these techniques to finitely presented non-free groups, in particular to 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.
In addition to testing these techniques on several well-known finitely presented groups, we introduce a new family of metabelian groups for which we analyze the computational complexity of the conjugacy search problem. We prove that for the family in general the time complexity of the conjugacy search problem is exponential, while for a subfamily the problem is polynomial. We also show that for some of these groups the conjugacy search problem is an instance of the discrete logarithm problem.
We also apply machine learning techniques to solving the conjugacy search problem. For each platform group we train a N-tuple regression network that can produce a candidate conjugator for a pair of conjugate elements. This candidate is then used as the initial state of a local search for a conjugator in the Cayley graph, in what we call regression-based conjugacy search (RBCS). RBCS can be applied to groups such as polycyclic groups for which other heuristic approaches, such as the length-based attack, are ineffective.
"],"dc:identifier":["https://academicworks.cuny.edu/gc_etds/2045"],"dc:subject":["Algebra","Artificial Intelligence and Robotics","Discrete Mathematics and Combinatorics","Theory and Algorithms","group theory","machine learning","non-commutative cryptography","conjugacy","polycyclic group"],"dc:title":["Solving Algorithmic Problems in Finitely Presented Groups via Machine Learning"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Doctoral"],"thesis:degree_name":["Doctor of Philosophy"],"thesis:institution_name":["The Graduate School and University Center of The City University of New York"]},"updated_at":"2026-07-24T01:59:30Z"}