4 papers · 1 filter
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…
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…
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach
George Giapitzakis, Kimon Fountoulakis, Eshaan Nichani +1
Semiautomata form a rich class of sequence-processing algorithms with applications in natural language processing, robotics, computational biology, and data mining. We establish th…
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…