2 citations · 2 across the 16 of their papers we have counts for
18 papers
Transformer Heads Looking for Order
Jasper van Doornmalen, Alexander Kozachinskiy, Corinna Mathwieser +4
In this note, we show that the problem of checking, whether a sequence of bits is ordered, is not doable by 1-head 1-layer transformers but is doable by a 2-head 1-layer transforme…
Indexing: the Beginning and the End
Alexander Kozachinskiy, Vicente Opazo, Felipe Urrutia
We study information bottlenecks in modern deep-learning architectures -- RNNs, softmax transformers, linear-attention transformers and state-space models -- through the lens of th…
Parity, Sensitivity, and Transformers
Alexander Kozachinskiy, Tomasz Steifer, Przemysław Wałȩga
Understanding what neural architectures can and cannot compute is a central challenge in the theory of AI. One of the fundamental problems in this context is the PARITY task, which…
Language Generation: Complexity Barriers and Implications for Learning
Marcelo Arenas, Pablo Barceló, Luis Cofré +1
Kleinberg and Mullainathan showed that language generation in the limit is always possible at the level of computability: given enough positive examples, a learner can eventually g…
Decoupling Positional and Symbolic Attention Behavior in Transformers
Felipe Urrutia, Jorge Salas, Alexander Kozachinskiy +3
An important aspect subtending language understanding and production is the ability to independently encode positional and symbolic information of the words within a sentence. In T…
Message Passing on the Edge: Towards Scalable and Expressive GNNs
Pablo Barceló, Fabian Jogl, Alexander Kozachinskiy +3
Graph neural networks (GNNs) are widely used in graph learning and most architectures propagate information by passing messages between vertices. In this work, we shift our attenti…
All Kolmogorov complexity functions are optimal, but are some more optimal?
Bruno Bauwens, Alexander Kozachinskiy, Alexander Shen
Kolmogorov (1965) defined the complexity of a string as the minimal length of a program generating . Obviously this definition depends on the choice of the programming langu…
Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Models
Hector Pasten, Felipe Urrutia, Hector Jimenez +3
Understanding how Transformers work and how they process information is key to the theoretical and empirical advancement of these machines. In this work, we demonstrate the existen…
A completely uniform transformer for parity
Alexander Kozachinskiy, Tomasz Steifer
We construct a 3-layer constant-dimension transformer, recognizing the parity language, where neither parameter matrices nor the positional encoding depend on the input length. Thi…
Strassen Attention, Split VC Dimension and Compositionality in Transformers
Alexander Kozachinskiy, Felipe Urrutia, Hector Jimenez +6
We propose the first method to show theoretical limitations for one-layer softmax transformers with arbitrarily many precision bits (even infinite). We establish those limitations…
Ehrenfeucht-Haussler Rank and Chain of Thought
Pablo Barceló, Alexander Kozachinskiy, Tomasz Steifer
The notion of \emph{rank} of a Boolean function has been a cornerstone in PAC learning theory, enabling quasipolynomial-time learning algorithms for polynomial-size decision trees.…
Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations
Pablo Barceló, Alexander Kozachinskiy, Miguel Romero Orth +2
Despite the wide use of -Nearest Neighbors as classification models, their explainability properties remain poorly understood from a theoretical perspective. While nearest neigh…
Optimal bounds for dissatisfaction in perpetual voting
Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer
In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proport…
Effective Littlestone Dimension
Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer
Delle Rose et al.~(COLT'23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learn…
On dimensionality of feature vectors in MPNNs
César Bravo, Alexander Kozachinskiy, Cristóbal Rojas
We revisit the classical result of Morris et al.~(AAAI'19) that message-passing graphs neural networks (MPNNs) are equal in their distinguishing power to the Weisfeiler--Leman (WL)…
Simple online learning with consistent oracle
Alexander Kozachinskiy, Tomasz Steifer
We consider online learning in the model where a learning algorithm can access the class only via the \emph{consistent oracle} -- an oracle, that, at any moment, can give a functio…
Three iterations of -WL test distinguish non isometric clouds of -dimensional points
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas +2
The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph ne…
Find a witness or shatter: the landscape of computable PAC learning
Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas +1
This paper contributes to the study of CPAC learnability -- a computable version of PAC learning -- by solving three open questions from recent papers. Firstly, we prove that every…