Showing 2026Show all
2 papers · 1 filter
cs.AI2026
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…
stat.ML2026
Tight Sample Complexity for Low-Degree and Sparse Boolean Polynomials
Jasper van Doornmalen, Mathieu Molina, Victor Verdugo +1
Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing th…