2 citations · 4 across the 8 of their papers we have counts for
8 papers
Length Generalization for Transformers via Compression
Georg Zetzsche, Hongjian Jiang, Andy Yang +4
Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a…
The Polynomial Counting Capabilities of Message Passing Neural Networks
Marco Sälzer, Pascal Bergsträßer, Anthony W. Lin
The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshol…
Length Generalization Bounds for Transformers
Andy Yang, Pascal Bergsträßer, Georg Zetzsche +2
Length generalization is a key property of a learning algorithm that enables it to make correct predictions on inputs of any length, given finite training data. To provide such a g…
Transformers are Inherently Succinct
Pascal Bergsträßer, Ryan Cotterell, Anthony W. Lin
We study succinctness as a measure of the expressive power of transformers. Succinctness -- how compactly a formalism can describe a language relative to other formalisms -- is a c…
The Power of Hard Attention Transformers on Data Sequences: A Formal Language Theoretic Perspective
Pascal Bergsträßer, Chris Köcher, Anthony Widjaja Lin +1
Formal language theory has recently been successfully employed to unravel the power of transformer encoders. This setting is primarily applicable in Natural Language Processing (NL…
Ramsey Quantifiers in Linear Arithmetics
Pascal Bergsträßer, Moses Ganardi, Anthony W. Lin +1
We study Satisfiability Modulo Theories (SMT) enriched with the so-called Ramsey quantifiers, which assert the existence of cliques (complete graphs) in the graph induced by some f…
Revisiting Membership Problems in Subclasses of Rational Relations
Pascal Bergsträßer, Moses Ganardi
We revisit the membership problem for subclasses of rational relations over finite and infinite words: Given a relation R in a class C_2, does R belong to a smaller class C_1? The…
Ramsey Quantifiers over Automatic Structures: Complexity and Applications to Verification
Pascal Bergsträßer, Moses Ganardi, Anthony W. Lin +1
Automatic structures are infinite structures that are finitely represented by synchronized finite-state automata. This paper concerns specifically automatic structures over finite…