Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
According to a well known theorem of Haussler and Welzl (1987), any range space of bounded VC-dimension admits an epsilon-net of size O (1/epsilon log 1/epsilon). Using probabilistic techniques, Pach and Woeginger (1990) showed that there exist range spaces of VC-dimension 2, for which the above bound is sharp. The only known range spaces of small VC-dimension, in which the ranges are geometric objects in some Euclidean space and the size of the smallest epsilon-nets is superlinear in 1/epsilon, were found by Alon (2010). In his examples, every epsilon-net is of size Omega (1/epsilon g(1/epsilon)), where g is an extremely slowly growing function, related to the inverse Ackermann function.
Thanh Trung Huynh, Quoc Viet Hung Nguyen, Thành Tâm Nguyên
Romain Christophe Rémy Fleury, Haoye Qin, Aleksi Antoine Bossart, Zhechen Zhang