-
Bonamy M., Bonnet E., Bousquet N., Charbit P., Giannopoulos P., Kim E., Rzazewski P., Sikora F., Thomassé S. (2021), EPTAS and Subexponential Algorithm for Maximum Clique on Disk and Unit Ball Graphs, Journal of the ACM (JACM), 68, 2, p. 1â38
A (unit) disk graph is the intersection graph of closed (unit) disks in the plane. Almost three decades ago, an elegant polynomial-time...
-
Bonnet E., Geniet C., Kim E., Thomassé S., Watrigant R. (2021), Twin-width III: Max Independent Set and Coloring, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
We recently introduced the graph invariant twin-width, and showed that first-order model checking can be solved in time f(d,k)n for...
-
Meunier L., Scetbon M., Pinot R., Atif J., Chevaleyre Y. (2021), Mixed Nash Equilibria in the Adversarial Examples Game, Preprint Lamsade, Paris
This paper tackles the problem of adversarial examples from a game theoretic point of view. We study the open question of the existence of...
-
Meunier L., Legheraba I., Chevaleyre Y., Teytaud O. (2021), Asymptotic convergence rates for averaging strategies, FOGA '21: Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms, Austria
Parallel black box optimization consists in estimating the optimum of a function using ? parallel evaluations of f. Averaging the ? best...
-
Araújo A., Negrevergne B., Chevaleyre Y., Atif J. (2021), On Lipschitz Regularization of Convolutional Layers using Toeplitz Matrix Theory, 35th AAAI Conference on Artificial Intelligence, Vancouver, Canada
This paper tackles the problem of Lipschitz regularization of Convolutional Neural Networks. Lipschitz regularity is now established as a...