# Learning the Word Problem: Geodesic Lengths and Cryptographic Applications

arXiv: https://arxiv.org/abs/2607.26241 · HTML: https://mlsanity.com/paper/2607.26241/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 88 references that are in the map.
- First posted on arXiv 28 Jul 2026.

## Builds on (most cited first, 17 of 17)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [Graph Contrastive Learning with Augmentations](https://mlsanity.com/paper/2010.13902/) (2020)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Strategies for Pre-training Graph Neural Networks](https://mlsanity.com/paper/1905.12265/) (2019)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [AlgebraNets](https://mlsanity.com/paper/2006.07360/) (2020)
- [A Machine Learning Approach That Beats Large Rubik's Cubes](https://mlsanity.com/paper/2502.13266/) (2025)
- [Solving the Conjugacy Decision Problem via Machine Learning](https://mlsanity.com/paper/1705.10417/) (2017)
- [Learning the symmetric group: large from small](https://mlsanity.com/paper/2502.12717/) (2025)
- [An application of neural networks to a problem in knot theory and group theory (untangling braids)](https://mlsanity.com/paper/2206.05373/) (2022)
- [Cryptography with right-angled Artin groups](https://mlsanity.com/paper/1610.06495/) (2016)
- [Node Classification and Search on the Rubik's Cube Graph with GNNs](https://mlsanity.com/paper/2501.18580/) (2025)

## Abstract (arXiv)

The Word Problem has been a subject of intensive mathematical study for over a century, initially driving advances in combinatorial group theory and more recently emerging as a foundational hardness assumption in post-quantum cryptography (PQC). While generally undecidable, several families of infinite non-abelian groups exhibit solvable or algorithmically fast word problems, making them attractive platforms for cryptographic design. This paper introduces WPNet, a novel Graph Neural Network architecture capable of solving the Word Problem heuristically, which is demonstrated on the Baumslag-Solitar group BS(1,2) and on an Artin group. By mapping unreduced words to dynamic graph structures, the model learns to cluster algebraically equivalent elements in a continuous embedding space, effectively identifying the geodesic representative of a word without executing discrete reduction steps. As an application, a model variant is developed that can predict the geodesic length of an unreduced word in both groups. To demonstrate the cryptographic severity of this structural leakage, WPNet is successfully deployed against the Wagner-Magyarik public-key cryptosystem.