4 papers
Paths, Ends and The Separation Problem for Infinite Graphs
Nicanor Carrasco-Vargas, Valentino Delle Rose, Cristóbal Rojas
We introduce and study the Separation Problem for infinite graphs, which involves determining whether a connected graph splits into at least two infinite connected components after…
On statistical learning of graphs
Vittorio Cipriani, Valentino Delle Rose, Luca San Mauro +1
We study PAC and online learnability of hypothesis classes formed by copies of a countably infinite graph G, where each copy is induced by permuting G's vertices. This corresponds…
Three iterations of -WL test distinguish non isometric clouds of -dimensional points
Valentino Delle Rose, Alexander Kozachinskiy, Cristóbal Rojas +2
The Weisfeiler--Lehman (WL) test is a fundamental iterative algorithm for checking isomorphism of graphs. It has also been observed that it underlies the design of several graph ne…
Effective Littlestone Dimension
Valentino Delle Rose, Alexander Kozachinskiy, Tomasz Steifer
Delle Rose et al.~(COLT'23) introduced an effective version of the Vapnik-Chervonenkis dimension, and showed that it characterizes improper PAC learning with total computable learn…