5 papers
Learning to Execute Graph Algorithms Exactly with Graph Neural Networks
Muhammad Fetrat Qharabagh, Artur Back de Luca, George Giapitzakis +1
Understanding what graph neural networks can learn, especially their ability to learn to execute algorithms, remains a central theoretical challenge. In this work, we prove exact l…
Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization
Artur Back de Luca, Kimon Fountoulakis
As state-of-the-art neural networks are deployed on reasoning and algorithmic tasks, exactness guarantees become increasingly important. However, high average-case accuracy can sti…
Learning to Add, Multiply, and Execute Algorithmic Instructions Exactly with Neural Networks
Artur Back de Luca, George Giapitzakis, Kimon Fountoulakis
Neural networks are known for their ability to approximate smooth functions, yet they fail to generalize perfectly to unseen inputs when trained on discrete operations. Such operat…
Positional Attention: Expressivity and Learnability of Algorithmic Computation
Artur Back de Luca, George Giapitzakis, Shenghao Yang +2
There is a growing interest in the ability of neural networks to execute algorithmic tasks (e.g., arithmetic, summary statistics, and sorting). The goal of this work is to better u…
Simulation of Graph Algorithms with Looped Transformers
Artur Back de Luca, Kimon Fountoulakis
The execution of graph algorithms using neural networks has recently attracted significant interest due to promising empirical progress. This motivates further understanding of how…