Machine learning for modular multiplication

Solomon Kullback and Richard A. Leibler. On information and sufficiency. Annals of Mathematical Statistics . 22

1951

Earlier work this paper cites.

Taher ElGamal. A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory 31

1985

Earlier work this paper cites.

Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84–93

2005

Earlier work this paper cites.

Theodoros Palamas. Investigating the Ability of Neural Networks to Learn Simple Modular Arithmetic. MSc Thesis, Edinburgh, 2017. Available at https://project-archive.inf.ed.ac.uk/msc/20172390/msc_proj.pdf

2017

Earlier work this paper cites.

Alethea Power, Yuri Burda, Harri Edwards, Igor Babuschkin and Vedant Misra. Grokking: Generalization beyond overfitting on small algorithmic datasets. 1st Mathematical Reasoning in General Artificial Intelligence Workshop, ICLR 2021

2021

Earlier work this paper cites.

François Charton. Linear algebra with transformers. Transactions on Machine Learning Research , 2835–8856 (2022)

2022

Cited alongside, same era.

Evrard Garcelon, Mohamed Malhou, Matteo Pirotta, Cathy Yuanchen Li, François Charton and Kristin Lauter. Solving Learning with Errors with Circular Regression. Preprint, Meta AI Papers, October 2022

2022

Cited alongside, same era.

Emily Wenger, Mingjie Chen, François Charton and Kristin Lauter. SALSA: Attacking Lattice Cryptography with Transformers. Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS) , November 2022

2022

Cited alongside, same era.

Andrey Gromov. Grokking modular arithmetic. Preprint (2023). Available at https://arxiv.org/abs/2301.02679

Original

2023

Cited alongside, same era.

Samy Jelassi, Stéphane d’Ascoli, Carles Domingo-Enrich, Yuhuai Wu, Yuanzhi Li and François Charton. Length Generalization in Arithmetic Transformers. Preprint (2023). Available at https://arxiv.org/abs/2306.15400

Cathy Yuanchen Li, Jana Sotáková, Emily Wenger, Mohamed Malhou, Evrard Garcelon, François Charton and Kristin Lauter. SALSA PICANTE: a machine learning attack on LWE with binary secrets. Proceedings of the ACM Conference on Computer and Communications Security (CCS) , November 2023

2023

Later among the works it cites.

Cathy Yuanchen Li, Emily Wenger, Zeyuan Allen-Zhu, François Charton and Kristin Lauter. SALSA VERDE - A machine learning attack on LWE with small sparse secrets. Proceedings of the 37th Conference on Neural Information Processing Systems (NeurIPS) , November 2023

2023

Later among the works it cites.

Neel Nanda, Lawrence Chan, Tom Lieberum, Jess Smith and Jacob Steinhardt. Progress measures for grokking via mechanistic interpretability. The Eleventh International Conference on Learning Representations , 2023

2023

Later among the works it cites.

Ruoqi Shen, Sébastien Bubeck, Ronen Eldan, Yin Tat Lee, Yuanzhi Li and Yi Zhang. Positional Description Matters for Transformers Arithmetic. Preprint (2023), available at https://arxiv.org/abs/2311.14737