15:00
Learning Group Geometry: Graph Embeddings for the Word Problem, Cryptanalysis, and Group Invariants
Abstract
This talk presents a geometric machine learning framework for resolving algebraic decision problems, with a focus on the Word Problem and post-quantum cryptography. Unreduced words in the Baumslag-Solitar group BS(1,2) and Artin groups are mapped into graphs constructed by their specific generators and defining relations.
To construct a continuous representation of the underlying group, a Graph Neural Network is trained using contrastive triplets (W,P,N). In this setup, W represents a base word, P is a positive example (a word algebraically equivalent to W), and N acts as a negative decoy (a non-equivalent word). The network embeds these graphs into a 128-dimensional unit sphere, forcing algebraically identical elements to cluster together while separating distinct elements.
This learned geometric space offers direct computational solutions to classical group-theoretic problems. It is used to successfully launch a cryptanalytic attack on the Wagner-Magyarik cryptosystem. Furthermore, by directly linking the continuous embedding back to the discrete metric space of the group, a variant network architecture accurately predicts the reduced geodesic length of randomly generated sequences.
The framework is subsequently applied to Right-Angled Artin Groups (RAAGs) and random Artin groups to evaluate the Nielsen equivalence of subgroup generating sets. The presentation concludes by outlining how these structural graph representations can be adapted to estimate Gromov hyperbolicity and extract other coarse geometric invariants from infinite groups.