Ferdinando Cicalese
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Ferdinando Cicalese has a total of 51 co-authors. Here are the top co-authors by number of shared publications:
- Eduardo Laber
PUC-Rio Brazil
12 shared publications - Martin Milanič
University of Primorska
8 shared publications - Manuele Bicego
Department of Computer Science, University of Verona, Verona, Italy
7 shared publications - Ugo Vaccaro
Department of Computer Science, University of Salerno, Fisciano, Italy
6 shared publications Luisa Gargano
Dipartimento di Informatica, Università di Salerno, Fisciano, Italy
4 shared publications- Luisa Gargano
University of Salerno
4 shared publications
Latest Publications
- 10 June 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. PP (01628828) , 1-12
A Theoretical Characterization of the Good Properties of Extremely Randomized Trees for Random Forest-Distance Computation
Ensembles of Extremely Randomized Trees (ERT), initially introduced for supervised scenarios, have been shown to represent surprisingly effective models also in unsupervised contexts, for example, for the detection of anomalies (i.e., Isolation Forests) or for defining Random Forest-distances. In this paper, we focus on this last field, providing a theoretical characterization to support the excellent empirical behaviors shown by ERTs in the definition of RF-distances. We start by assuming the existence, in a given domain, of a proper representation, i.e., a vectorial representation fulfilling the Compactness Hypothesis given by Arkadev and Braverman in 1967. Then, given the “true” distance between a pair of objects, we show that it is possible to derive a bound on the approximation guaranteed by an ERT-based RF-distance with respect to such true measure. In words, we show that it is possible to compute a constant $c$ such that, if a pair of objects are $\epsilon$-close in the true distance, then, with high probability, they are $(c \cdot \epsilon )$-close also in the ERT-based RF-distance.
- 10 June 2026
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. PP (01628828) , 1-12
A Theoretical Characterization of the Good Properties of Extremely Randomized Trees for Random Forest-Distance Computation
Ensembles of Extremely Randomized Trees (ERT), initially introduced for supervised scenarios, have been shown to represent surprisingly effective models also in unsupervised contexts, for example, for the detection of anomalies (i.e., Isolation Forests) or for defining Random Forest-distances. In this paper, we focus on this last field, providing a theoretical characterization to support the excellent empirical behaviors shown by ERTs in the definition of RF-distances. We start by assuming the existence, in a given domain, of a proper representation, i.e., a vectorial representation fulfilling the Compactness Hypothesis given by Arkadev and Braverman in 1967. Then, given the “true” distance between a pair of objects, we show that it is possible to derive a bound on the approximation guaranteed by an ERT-based RF-distance with respect to such true measure. In words, we show that it is possible to compute a constant $c$ such that, if a pair of objects are $\epsilon$-close in the true distance, then, with high probability, they are $(c \cdot \epsilon )$-close also in the ERT-based RF-distance.
- 30 December 2025
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 84
Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification
We present Probabilistically Tightened Linear Relaxation-based Perturbation Analysis (PT-LiRPA), a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets. In detail, we show that with negligible computational overhead, PT-LiRPA exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output, reducing the computational cost of formal verification tools while providing probabilistic guarantees on verification soundness. Extensive experiments on standard formal verification benchmarks, including the International Verification of Neural Networks Competition, show that our PT-LiRPA-based verifier improves robustness certificates, i.e., the certified lower bound of ε perturbation tolerated by the models, by up to 3.31X and 2.26X compared to related work. Importantly, our probabilistic approach results in a valuable solution for challenging competition entries where state-of-the-art formal verification methods fail, allowing us to provide answers with high confidence (i.e., at least 99%).
- 30 December 2025
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 84
Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification
We present Probabilistically Tightened Linear Relaxation-based Perturbation Analysis (PT-LiRPA), a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets. In detail, we show that with negligible computational overhead, PT-LiRPA exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output, reducing the computational cost of formal verification tools while providing probabilistic guarantees on verification soundness. Extensive experiments on standard formal verification benchmarks, including the International Verification of Neural Networks Competition, show that our PT-LiRPA-based verifier improves robustness certificates, i.e., the certified lower bound of ε perturbation tolerated by the models, by up to 3.31X and 2.26X compared to related work. Importantly, our probabilistic approach results in a valuable solution for challenging competition entries where state-of-the-art formal verification methods fail, allowing us to provide answers with high confidence (i.e., at least 99%).
- Open Access
- 8 December 2025
- Published by Elsevier in Artificial Intelligence
- Vol. 351
Probabilistically robust counterfactual explanations under model changes
- 8 December 2025
- Published by Elsevier in Artificial Intelligence
- Vol. 351
Open AccessProbabilistically robust counterfactual explanations under model changes
- Open Access
- 18 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Intelligent Systems and Technology
- Vol. 17 (1) , 1-27
Verifying Online Safety Properties for Safe Deep Reinforcement Learning
Ensuring safety in reinforcement learning (RL) is critical for deploying agents in real-world applications. During training, current safe RL approaches often rely on indicator cost functions that provide sparse feedback, resulting in two key limitations: (i) poor sample efficiency due to the lack of safety information in neighboring states, and (ii) dependence on cost-value functions, leading to brittle convergence and suboptimal performance. After training, safety is guaranteed via formal verification (FV) methods for deep neural networks, whose computational complexity hinders their application during training. We address the limitations of using cost functions via verification by proposing a safe RL method based on a violation value—the risk associated with policy decisions in a portion of the state space. Our approach verifies safety properties (i.e., state-action pairs) that may lead to unsafe behavior, and quantifies the size of the state space where properties are violated. This violation value is then used to penalize the agent during training to encourage safer policy behavior. Given the NP-hard nature of FV, we propose an efficient, sample-based approximation with probabilistic guarantees to compute the violation value. Extensive experiments on standard benchmarks and real-world robotic navigation tasks show that violation-augmented approaches significantly improve safety by reducing the number of unsafe states encountered while achieving superior performance compared to existing methods.
- 18 November 2025
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Intelligent Systems and Technology
- Vol. 17 (1) , 1-27
Open AccessVerifying Online Safety Properties for Safe Deep Reinforcement Learning
Ensuring safety in reinforcement learning (RL) is critical for deploying agents in real-world applications. During training, current safe RL approaches often rely on indicator cost functions that provide sparse feedback, resulting in two key limitations: (i) poor sample efficiency due to the lack of safety information in neighboring states, and (ii) dependence on cost-value functions, leading to brittle convergence and suboptimal performance. After training, safety is guaranteed via formal verification (FV) methods for deep neural networks, whose computational complexity hinders their application during training. We address the limitations of using cost functions via verification by proposing a safe RL method based on a violation value—the risk associated with policy decisions in a portion of the state space. Our approach verifies safety properties (i.e., state-action pairs) that may lead to unsafe behavior, and quantifies the size of the state space where properties are violated. This violation value is then used to penalize the agent during training to encourage safer policy behavior. Given the NP-hard nature of FV, we propose an efficient, sample-based approximation with probabilistic guarantees to compute the violation value. Extensive experiments on standard benchmarks and real-world robotic navigation tasks show that violation-augmented approaches significantly improve safety by reducing the number of unsafe states encountered while achieving superior performance compared to existing methods.
- Open Access
On constrained intersection representations of graphs and digraphs
We study the problem of determining optimal directed intersection representations of DAGs in a model introduced by Kostochka, Liu, Machado, and Milenkovic [ISIT2019]: vertices are assigned color sets so that there is an arc from a vertex $u$ to a vertex $v$ if and only if their color sets have nonempty intersection and $v$ gets assigned strictly more colors than $u$, and the goal is to minimize the total number of colors. We show that the problem is polynomially solvable in the class of triangle-free and Hamiltonian DAGs and also disclose the relationship of this problem with several other models of intersection representations of graphs and digraphs.Open AccessOn constrained intersection representations of graphs and digraphs
We study the problem of determining optimal directed intersection representations of DAGs in a model introduced by Kostochka, Liu, Machado, and Milenkovic [ISIT2019]: vertices are assigned color sets so that there is an arc from a vertex $u$ to a vertex $v$ if and only if their color sets have nonempty intersection and $v$ gets assigned strictly more colors than $u$, and the goal is to minimize the total number of colors. We show that the problem is polynomially solvable in the class of triangle-free and Hamiltonian DAGs and also disclose the relationship of this problem with several other models of intersection representations of graphs and digraphs. - 31 January 2025
- Published by Springer Nature
- p. 188-198
An Interesting Property of Random Forest Distances with Respect to the Curse of Dimensionality
- 31 January 2025
- Published by Springer Nature
- p. 188-198
An Interesting Property of Random Forest Distances with Respect to the Curse of Dimensionality
- 27 July 2024
- Published by Springer Nature
- p. 114-130
On the Complexity and Approximability of Bounded Access Lempel Ziv Coding
- 27 July 2024
- Published by Springer Nature
- p. 114-130
On the Complexity and Approximability of Bounded Access Lempel Ziv Coding
- Open Access
- 19 June 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 18 (7) , 1-18
Computing Random Forest-distances in the presence of missing data
In this article, we study the problem of computing Random Forest-distances in the presence of missing data. We present a general framework which avoids pre-imputation and uses in an agnostic way the information contained in the input points. We centre our investigation on RatioRF, an RF-based distance recently introduced in the context of clustering and shown to outperform most known RF-based distance measures. We also show that the same framework can be applied to several other state-of-the-art RF-based measures and provide their extensions to the missing data case. We provide significant empirical evidence of the effectiveness of the proposed framework, showing extensive experiments with RatioRF on 15 datasets. Finally, we also positively compare our method with many alternative literature distances, which can be computed with missing values.
- 19 June 2024
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Knowledge Discovery From Data
- Vol. 18 (7) , 1-18
Open AccessComputing Random Forest-distances in the presence of missing data
In this article, we study the problem of computing Random Forest-distances in the presence of missing data. We present a general framework which avoids pre-imputation and uses in an agnostic way the information contained in the input points. We centre our investigation on RatioRF, an RF-based distance recently introduced in the context of clustering and shown to outperform most known RF-based distance measures. We also show that the same framework can be applied to several other state-of-the-art RF-based measures and provide their extensions to the missing data case. We provide significant empirical evidence of the effectiveness of the proposed framework, showing extensive experiments with RatioRF on 15 datasets. Finally, we also positively compare our method with many alternative literature distances, which can be computed with missing values.
- Open Access
On the complexity and approximability of Bounded access Lempel Ziv coding
We study the complexity of constructing an optimal parsing $\varphi$ of a string ${\bf s} = s_1 \dots s_n$ under the constraint that given a position $p$ in the original text, and the LZ76-like (Lempel Ziv 76) encoding of $T$ based on $\varphi$, it is possible to identify/decompress the character $s_p$ by performing at most $c$ accesses to the LZ encoding, for a given integer $c.$ We refer to such a parsing $\varphi$ as a $c$-bounded access LZ parsing or $c$-BLZ parsing of ${\bf s}.$ We show that for any constant $c$ the problem of computing the optimal $c$-BLZ parsing of a string, i.e., the one with the minimum number of phrases, is NP-hard and also APX hard, i.e., no PTAS can exist under the standard complexity assumption $P \neq NP.$ We also study the ratio between the sizes of an optimal $c$-BLZ parsing of a string ${\bf s}$ and an optimal LZ76 parsing of ${\bf s}$ (which can be greedily computed in polynomial time).Open AccessOn the complexity and approximability of Bounded access Lempel Ziv coding
We study the complexity of constructing an optimal parsing $\varphi$ of a string ${\bf s} = s_1 \dots s_n$ under the constraint that given a position $p$ in the original text, and the LZ76-like (Lempel Ziv 76) encoding of $T$ based on $\varphi$, it is possible to identify/decompress the character $s_p$ by performing at most $c$ accesses to the LZ encoding, for a given integer $c.$ We refer to such a parsing $\varphi$ as a $c$-bounded access LZ parsing or $c$-BLZ parsing of ${\bf s}.$ We show that for any constant $c$ the problem of computing the optimal $c$-BLZ parsing of a string, i.e., the one with the minimum number of phrases, is NP-hard and also APX hard, i.e., no PTAS can exist under the standard complexity assumption $P \neq NP.$ We also study the ratio between the sizes of an optimal $c$-BLZ parsing of a string ${\bf s}$ and an optimal LZ76 parsing of ${\bf s}$ (which can be greedily computed in polynomial time). - 18 September 2023
- Published by Springer Nature
- p. 645-660
On the Good Behaviour of Extremely Randomized Trees in Random Forest-Distance Computation
- 18 September 2023
- Published by Springer Nature
- p. 645-660
On the Good Behaviour of Extremely Randomized Trees in Random Forest-Distance Computation