3 papers
math.LO2023
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…
cs.CC2023
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…
math.LO2021
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.…