4 papers
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.…