1 citations · 2 across the 12 of their papers we have counts for
15 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…
Mirror, Mirror on the Wall: Prompt Echoing in Small Instruct Language Models
Inez Okulska, Bartosz Naskręcki, Jan Piotrowski +1
Prompt echoing is a recognized failure mode of instruct language models, in which a model instead of generating a response, mirrors the provided prompt, even though it did not rece…
Provably Shorter Scratchpads in Hybrid DeltaNet-Attention Decoders
Tomasz Steifer
We investigate the expressive power of hybrid recurrent-attention decoders, a class of architectures used in recent open-source language models such as Qwen3-Next and its successor…
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…
Computable universal online learning
Dariusz Kalociński, Tomasz Steifer
Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learni…
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…
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…
Learning Equivalence Relations on Polish Spaces
Dino Rossegger, Theodore Slaman, Tomasz Steifer
We investigate natural variations of behaviourally correct learning and explanatory learning -- two learning paradigms studied in algorithmic learning theory -- that allow us to ``…
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…
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…
No Agreement Without Loss: Learning and Social Choice in Peer Review
Pablo Barceló, Mauricio Duarte, Cristóbal Rojas +1
In peer review systems, reviewers are often asked to evaluate various features of submissions, such as technical quality or novelty. A score is given to each of the predefined feat…
Probabilistic vs deterministic gamblers
Laurent Bienvenu, Valentino Delle Rose, Tomasz Steifer
Can a probabilistic gambler get arbitrarily rich when all deterministic gamblers fail? We study this problem in the context of algorithmic randomness, introducing a new notion -- a…
Universal Coding and Prediction on Ergodic Martin-Löf Random Points
Łukasz Dębowski, Tomasz Steifer
Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to m…