1 citations · 1 across the 3 of their papers we have counts for
7 papers
Cross-Attention and Encoder-Decoder Transformers: A Logical Characterization
Veeti Ahvonen, Damian Heiman, Antti Kuusisto +2
We give a novel logical characterization of encoder-decoder transformers, the foundational architecture for LLMs that also sees use in various settings that benefit from cross-atte…
Expressive Power of Graph Transformers via Logic
Veeti Ahvonen, Maurice Funk, Damian Heiman +2
Transformers are the basis of modern large language models, but relatively little is known about their precise expressive power on graphs. We study the expressive power of graph tr…
Formula size game and model checking for modal substitution calculus
Veeti Ahvonen, Reijo Jaakkola, Antti Kuusisto
Recent research has applied modal substitution calculus (MSC) and its variants to characterize various computational frameworks such as graph neural networks (GNNs) and distributed…
Graph neural networks and MSO
Veeti Ahvonen, Damian Heiman, Antti Kuusisto
We give an alternative proof for the existing result that recurrent graph neural networks working with reals have the same expressive power in restriction to monadic second-order l…
Descriptive complexity for neural networks via Boolean networks
Veeti Ahvonen, Damian Heiman, Antti Kuusisto
We investigate the expressive power of neural networks from the point of view of descriptive complexity. We study neural networks that use floating-point numbers and piecewise poly…
Logical Characterizations of Recurrent Graph Neural Networks with Reals and Floats
Veeti Ahvonen, Damian Heiman, Antti Kuusisto +1
In pioneering work from 2019, Barceló and coauthors identified logics that precisely match the expressive power of constant iteration-depth graph neural networks (GNNs) relative t…