Showing 2026Show all
2 papers · 1 filter
cs.CC2026
Average Attention Transformers and Arithmetic Circuits
Lena Ehrmuth, Laura Strieker
We analyse the computational power of transformer encoders as sequence-to-sequence functions on vectors. We show that average hard attention can be used to simulate arithmetic circ…
cs.CC2026
Recurrent Graph Neural Networks and Arithmetic Circuits
Timon Barlag, Vivian Holzapfel, Laura Strieker +2
We characterise the computational power of recurrent graph neural networks (GNNs) in terms of arithmetic circuits over the real numbers. Our networks are not restricted to aggregat…