5 papers
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…
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…
Logical Approaches to Non-deterministic Polynomial Time over Semirings
Timon Barlag, Nicolas Fröhlich, Teemu Hankala +6
We provide a logical characterization of non-deterministic polynomial time defined by BSS machines over semirings via existential second-order logic interpreted in the semiring sem…
Logic and Computation through the Lens of Semirings
Timon Barlag, Nicolas Fröhlich, Teemu Hankala +6
We study the expressivity and computational aspects of first-order logic and its extensions in the semiring semantics developed by Grädel and Tannen. We characterize the complexit…
Graph Neural Networks and Arithmetic Circuits
Timon Barlag, Vivian Holzapfel, Laura Strieker +2
We characterize the computational power of neural networks that follow the graph neural network (GNN) architecture, not restricted to aggregate-combine GNNs or other particular typ…