5 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…
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…
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…
Randomized Binary and Tree Search under Pressure
Agustín Caracci, Christoph Dürr, José Verschae
We study a generalized binary search problem on the line and general trees. On the line (e.g., a sorted array), binary search finds a target node in queries in the wors…
Set Selection with Uncertain Weights: Non-Adaptive Queries and Thresholds
Christoph Dürr, Arturo Merino, José A. Soto +1
We study set selection problems where the weights are uncertain. Instead of its exact weight, only an uncertainty interval containing its true weight is available for each element.…