2 citations · 2 across the 9 of their papers we have counts for
10 papers
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…
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…
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…
Classifying word problems of finitely generated algebras via computable reducibility
Valentino Delle Rose, Luca San Mauro, Andrea Sorbi
We contribute to a recent research program which aims at revisiting the study of the complexity of word problems, a major area of research in combinatorial algebra, through the len…
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…
Find a witness or shatter: the landscape of computable PAC learning
Valentino Delle Rose, Alexander Kozachinskiy, Cristobal Rojas +1
This paper contributes to the study of CPAC learnability -- a computable version of PAC learning -- by solving three open questions from recent papers. Firstly, we prove that every…
Probabilistic vs deterministic gamblers
Laurent Bienvenu, Valentino Delle Rose, Tomasz Steifer
Can a probabilistic gambler get arbitrarily rich when all deterministic gamblers fail? We study this problem in the context of algorithmic randomness, introducing a new notion -- a…
Relativized depth
Laurent Bienvenu, Valentino Delle Rose, Wolfgang Merkle
Bennett's notion of depth is usually considered to describe the usefulness and internal organization of the information encoded into an object such as an infinite binary sequence.…
A note on the category of equivalence relations
Valentino Delle Rose, Luca San Mauro, Andrea Sorbi
We make some beginning observations about the category of equivalence relations on the set of natural numbers, where a morphism between two equivalence relat…
Word problems and ceers
Valentino Delle Rose, Luca San Mauro, Andrea Sorbi
This note addresses the issue as to which ceers can be realized by word problems of computably enumerable (or, simply, c.e.) structures (such as c.e. semigroups, groups, and rings)…