Ferdinando Cicalese

AAAI Conference 2026 Conference Paper

On the Probabilistic Learnability of Compact Neural Network Preimage Bounds

• Luca Marzari
• Manuele Bicego
• Ferdinando Cicalese
• Alessandro Farinelli

Although recent provable methods have been developed to compute preimage bounds for neural networks, their scalability is fundamentally limited by the #P-hardness of the problem. In this work, we adopt a novel probabilistic perspective, aiming to deliver solutions with high-confidence guarantees and bounded error. To this end, we investigate the potential of bootstrap-based and randomized approaches that are capable of capturing complex patterns in high-dimensional spaces, including input regions where a given output property holds. In detail, we introduce Random Forest Property Verifier (RF-ProVe), a method that exploits an ensemble of randomized decision trees to generate candidate input regions satisfying a desired output property and refines them through active resampling. Our theoretical derivations offer formal statistical guarantees on region purity and global coverage, providing a practical, scalable solution for computing compact preimage approximations in cases where exact solvers fail to scale.

AIJ Journal 2026 Journal Article

Probabilistically robust counterfactual explanations under model changes

• Luca Marzari
• Francesco Leofante
• Ferdinando Cicalese
• Alessandro Farinelli

We study the problem of generating robust counterfactual explanations for deep learning models subject to model changes. We focus on plausible model changes altering model parameters and propose a novel framework to reason about the robustness property in this setting. To motivate our solution, we begin by showing for the first time that computing the robustness of counterfactuals with respect to model changes is NP-hard. As this (practically) rules out the existence of scalable algorithms for exactly computing robustness, we propose a novel probabilistic approach which is able to provide tight estimates of robustness with strong guarantees while preserving scalability. Remarkably, and differently from existing solutions targeting plausible model changes, our approach does not impose requirements on the network to be analysed, thus enabling robustness analysis on a wider range of architectures, including state-of-the-art tabular transformers. A thorough experimental analysis on four binary classification datasets reveals that our method improves the state of the art in generating robust explanations, outperforming existing methods.

TCS Journal 2025 Journal Article

Decision trees with short explainable rules

• Victor F.C. Souza
• Ferdinando Cicalese
• Eduardo Sany Laber
• Marco Molinaro

Decision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretability/explainability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters. This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our new measure (which we call the explanation size) and the more classical measures of worst-case and average depth. We also show that from our characterizations it is possible to obtain polynomial algorithms that guarantee O ( ln ⁡ n ) -approximation (hence optimal if P ≠ N P ) for the minimization of both the average/worst-case explanation size and the average/worst-case depth.

I&C Journal 2025 Journal Article

Hardness and approximability of bounded access Lempel Ziv coding

• Ferdinando Cicalese
• Francesca Ugazio

We study the complexity of constructing an optimal parsing φ of a string s = s 1 … 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 φ, 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 φ as a c-bounded access LZ parsing or c-BLZ parsing of 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 P T A S can exist under the standard complexity assumption P ≠ N P. We also study the ratio between the sizes of an optimal c-BLZ parsing of a string s and an optimal LZ76 parsing of s (which can be greedily computed in polynomial time). For this we establish a non-trivial lower bound Ω ( | s | c + 1 ) on the size of an optimal parsing for a square free string s, and also show that such a lower bound is tight for a large class of (square free) morphic words. Finally, after showing that under ETH, every algorithm for c-BLZ requires time 2 Ω ( | s | 1 c ), hence strongly exponential in the special case c = 1, we show an algorithm matching this bound that can compute an optimal 1-BLZ parsing of a string s in time O ⁎ ( 1. 755 | s | ).

JAIR Journal 2025 Journal Article

Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification

• Luca Marzari
• Ferdinando Cicalese
• Alessandro Farinelli

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%).

TIST Journal 2025 Journal Article

Verifying Online Safety Properties for Safe Deep Reinforcement Learning

• Luca Marzari
• Ferdinando Cicalese
• Alessandro Farinelli
• Christopher Amato
• Enrico Marchesini

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.

AAAI Conference 2024 Conference Paper

Enumerating Safe Regions in Deep Neural Networks with Provable Probabilistic Guarantees

• Luca Marzari
• Davide Corsi
• Enrico Marchesini
• Alessandro Farinelli
• Ferdinando Cicalese

Identifying safe areas is a key point to guarantee trust for systems that are based on Deep Neural Networks (DNNs). To this end, we introduce the AllDNN-Verification problem: given a safety property and a DNN, enumerate the set of all the regions of the property input domain which are safe, i.e., where the property does hold. Due to the #P-hardness of the problem, we propose an efficient approximation method called ε-ProVe. Our approach exploits a controllable underestimation of the output reachable sets obtained via statistical prediction of tolerance limits, and can provide a tight —with provable probabilistic guarantees— lower estimate of the safe areas. Our empirical evaluation on different standard benchmarks shows the scalability and effectiveness of our method, offering valuable insights for this new type of verification of DNNs.

ECAI Conference 2024 Conference Paper

Rigorous Probabilistic Guarantees for Robust Counterfactual Explanations

• Luca Marzari
• Francesco Leofante
• Ferdinando Cicalese
• Alessandro Farinelli

We study the problem of assessing the robustness of counterfactual explanations for deep learning models. We focus on plausible model shifts altering model parameters and propose a novel framework to reason about the robustness property in this setting. To motivate our solution, we begin by showing for the first time that computing the robustness of counterfactuals with respect to plausible model shifts is NP-complete. As this (practically) rules out the existence of scalable algorithms for exactly computing robustness, we propose a novel probabilistic approach which is able to provide tight estimates of robustness with strong guarantees while preserving scalability. Remarkably, and differently from existing solutions targeting plausible model shifts, our approach does not impose requirements on the network to be analyzed, thus enabling robustness analysis on a wider range of architectures. Experiments on four binary classification datasets indicate that our method improves the state of the art in generating robust explanations, outperforming existing methods on a range of metrics.

TCS Journal 2023 Journal Article

Hardness and approximation of multiple sequence alignment with column score

• Andrea Caucchiolo
• Ferdinando Cicalese

Multiple Sequence Alignment (MSA for short) is a well known problem in the field of computational biology. In order to evaluate the quality of a solution, many different scoring functions have been introduced, the most widely used being the Sum-of-Pairs score (SP-score). It is known that computing the best MSA under the SP-score measure is NP-hard. In this paper, we introduce a variant of the Column score (defined in Thompson et al. 1999), which we refer to as Selective Column score: Given a symbol a ∈ Σ, the score of the i-th column is one if and only if all symbols of the same column are a, and otherwise zero. The a-column score of an alignment is then the number of columns made of only character a. We show that finding the optimal MSA under the Selective Column Score is NP-hard for all alphabets of size | Σ | ≥ 2, and that the associated maximization problem is poly-APX-hard. We also give an approximation algorithm that almost matches the inapproximability bound.

IJCAI Conference 2023 Conference Paper

The #DNN-Verification Problem: Counting Unsafe Inputs for Deep Neural Networks

• Luca Marzari
• Davide Corsi
• Ferdinando Cicalese
• Alessandro Farinelli

Deep Neural Networks are increasingly adopted in critical tasks that require a high level of safety, e. g. , autonomous driving. While state-of-the-art verifiers can be employed to check whether a DNN is unsafe w. r. t. some given property (i. e. , whether there is at least one unsafe input configuration), their yes/no output is not informative enough for other purposes, such as shielding, model selection, or training improvements. In this paper, we introduce the #DNN-Verification problem, which involves counting the number of input configurations of a DNN that result in a violation of a particular safety property. We analyze the complexity of this problem and propose a novel approach that returns the exact count of violations. Due to the #P-completeness of the problem, we also propose a randomized, approximate method that provides a provable probabilistic bound of the correct count while significantly reducing computational requirements. We present experimental results on a set of safety-critical benchmarks that demonstrate the effectiveness of our approximate method and evaluate the tightness of the bound.

NeurIPS Conference 2022 Conference Paper

Decision Trees with Short Explainable Rules

• Victor Feitosa Souza
• Ferdinando Cicalese
• Eduardo Laber
• Marco Molinaro

Decision trees are widely used in many settings where interpretable models are preferred or required. As confirmed by recent empirical studies, the interpretability/explanability of a decision tree critically depends on some of its structural parameters, like size and the average/maximum depth of its leaves. There is indeed a vast literature on the design and analysis of decision tree algorithms that aim at optimizing these parameters. This paper contributes to this important line of research: we propose as a novel criterion of measuring the interpretability of a decision tree, the sparsity of the set of attributes that are (on average) required to explain the classification of the examples. We give a tight characterization of the best possible guarantees achievable by a decision tree built to optimize both our newmeasure (which we call the {\em explanation size}) and the more classical measures of worst-case and average depth. In particular, we give an algorithm that guarantees $O(\ln n )$-approximation (hence optimal if $P \neq NP$) for the minimization of both the average/worst-case explanation size and the average/worst-case depth. In addition to our theoretical contributions, experiments with 20 real datasets show that our algorithm has accuracy competitive with CART while producing trees that allow for much simpler explanations.

TCS Journal 2021 Journal Article

On infinite prefix normal words

• Ferdinando Cicalese
• Zsuzsanna Lipták
• Massimiliano Rossi

Prefix normal words are binary words with the property that no factor has more 1s than the prefix of the same length. Finite prefix normal words were introduced in Fici and Lipták (2011) [18]. In this paper, we study infinite prefix normal words and explore their relationship to some known classes of infinite binary words. In particular, we establish a connection between prefix normal words and Sturmian words, between prefix normal words and abelian complexity, and between prefix normality and lexicographic order. 1

TCS Journal 2020 Journal Article

On the multi-interval Ulam-Rényi game: For 3 lies 4 intervals suffice

• Ferdinando Cicalese
• Massimiliano Rossi

We study the problem of identifying an initially unknown m-bit number by using yes-no questions when up to a fixed number e of the answers can be erroneous. In the variant we consider here questions are restricted to be the union of up to a fixed number of intervals. For any e ≥ 1 let k e be the minimum k such that for all sufficiently large m, there exists a strategy matching the information theoretic lower bound and only using k-interval questions. It is known that k e = O ( e 2 ) and it has been conjectured that the k e = Θ ( e ). This linearity conjecture is supported by the known results for small values of e as for e ≤ 2 we have k e = e. We focus on the case e = 3 and show k 3 ≤ 4 improving upon the previously known bound k 3 ≤ 10.

ICML Conference 2020 Conference Paper

Teaching with Limited Information on the Learner's Behaviour

• Ferdinando Cicalese
• Sergio Filho
• Eduardo Sany Laber
• Marco Molinaro 0001

Machine Teaching studies how efficiently a Teacher can guide a Learner to a target hypothesis. We focus on the model of Machine Teaching with a black box learner introduced in [Dasgupta et al. , ICML 2019], where the teaching is done interactively without having any knowledge of the Learner’s algorithm and class of hypotheses, apart from the fact that it contains the target hypothesis $h^*$. We first refine some existing results for this model and, then, we study new variants of it. Motivated by the realistic possibility that $h^*$ is not available to the learner, we consider the case where the teacher can only aim at having the learner converge to a best available approximation of $h^*$. We also consider weaker black box learners, where, in each round, the choice of the consistent hypothesis returned to the Teacher is not adversarial, and in particular, we show that better provable bounds can be obtained for a type of Learner that moves to the next hypothesis smoothly, preferring hypotheses that are close to the current one; and for another type of Learner that can provide to the Teacher hypotheses chosen at random among those consistent with the examples received so far. Finally, we present an empirical evaluation of our basic interactive teacher on real datasets.

ICML Conference 2019 Conference Paper

New results on information theoretic clustering

• Ferdinando Cicalese
• Eduardo Sany Laber
• Lucas Murtinho

We study the problem of optimizing the clustering of a set of vectors when the quality of the clustering is measured by the Entropy or the Gini impurity measure. Our results contribute to the state of the art both in terms of best known approximation guarantees and inapproximability bounds: (i) we give the first polynomial time algorithm for Entropy impurity based clustering with approximation guarantee independent of the number of vectors and (ii) we show that the problem of clustering based on entropy impurity does not admit a PTAS. This also implies an inapproximability result in information theoretic clustering for probability distributions closing a problem left open in [Chaudhury and McGregor, COLT08] and [Ackermann et al. , ECCC11]. We also report experiments with a new clustering method that was designed on top of the theoretical tools leading to the above results. These experiments suggest a practical applicability for our method, in particular, when the number of clusters is large.

TCS Journal 2018 Journal Article

Bubble-Flip—A new generation algorithm for prefix normal words

• Ferdinando Cicalese
• Zsuzsanna Lipták
• Massimiliano Rossi

We present a new recursive generation algorithm for prefix normal words. These are binary words with the property that no factor has more 1s than the prefix of the same length. The new algorithm uses two operations on binary words, which exploit certain properties of prefix normal words in a smart way. We introduce infinite prefix normal words and show that one of the operations used by the algorithm, if applied repeatedly to extend the word, produces an ultimately periodic infinite word, which is prefix normal. Moreover, based on the original finite word, we can predict both the length and the density of an ultimate period of this infinite word. 1

TCS Journal 2016 Journal Article

On the tree search problem with non-uniform costs

• Ferdinando Cicalese
• Balázs Keszegh
• Bernard Lidický
• Dömötör Pálvölgyi
• Tomáš Valla

Searching in partially ordered structures has been considered in the context of information retrieval and efficient tree-like indices, as well as in hierarchy based knowledge representation. In this paper we focus on tree-like partial orders and consider the problem of identifying an initially unknown vertex in a tree by asking edge queries: an edge query e returns the component of T − e containing the vertex sought for, while incurring some known cost c ( e ). The Tree Search Problem with Non-Uniform Cost is the following: given a tree T on n vertices, each edge having an associated cost, construct a strategy that minimizes the total cost of the identification in the worst case. Finding the strategy guaranteeing the minimum possible cost is an NP-complete problem already for input trees of degree 3 or diameter 6. The best known approximation guarantee was an O ( log ⁡ n / log ⁡ log ⁡ log ⁡ n ) -approximation algorithm of Cicalese et al. (2012) [4]. We improve upon the above results both from the algorithmic and the computational complexity point of view: We provide a novel algorithm that provides an O ( log ⁡ n log ⁡ log ⁡ n ) -approximation of the cost of the optimal strategy. In addition, we show that finding an optimal strategy is NP-hard even when the input tree is a spider of diameter 6, i. e. , at most one vertex has degree larger than 2.

TCS Journal 2015 Journal Article

On the complexity of the vector connectivity problem

• Ferdinando Cicalese
• Martin Milanič
• Romeo Rizzi

We study a relaxation of the Vector Domination problem called Vector Connectivity (VecCon). Given a graph G with a requirement r ( v ) for each vertex v, VecCon asks for a minimum cardinality set S of vertices such that every vertex v ∈ V ∖ S is connected to S via r ( v ) disjoint paths. In the paper introducing the problem, Boros et al. [4] gave polynomial-time solutions for VecCon in trees, cographs, and split graphs, and showed that the problem can be approximated in polynomial time on n-vertex graphs to within a factor of log ⁡ n + 2, leaving open the question of whether the problem is NP-hard on general graphs. We show that VecCon is APX-hard in general graphs, and NP-hard in planar bipartite graphs and in planar line graphs. We also generalize the polynomial result for trees by solving the problem for block graphs.

TCS Journal 2015 Journal Article

Spread of influence in weighted networks under time and budget constraints

• Ferdinando Cicalese
• Gennaro Cordasco
• Luisa Gargano
• Martin Milanič
• Joseph Peters
• Ugo Vaccaro

Given a network represented by a weighted directed graph G, we consider the problem of finding a bounded cost set of nodes S such that the influence spreading from S in G, within a given time bound, is as large as possible. The dynamics that governs the spread of influence is the following: initially only elements in S are influenced; subsequently at each round, the set of influenced elements is augmented by all nodes in the network that have a sufficiently large number of already influenced neighbors. We prove that the problem is NP-hard, even in simple networks like complete graphs and trees. We also derive a series of positive results. We present exact pseudo-polynomial time algorithms for general trees, that become polynomial time in case the trees are unweighted. This last result improves on previously published results. We also design polynomial time algorithms for general weighted paths and cycles, and for unweighted complete graphs.

TCS Journal 2014 Journal Article

Approximating the maximum consecutive subsums of a sequence

• Ferdinando Cicalese
• Eduardo Laber
• Oren Weimann
• Raphael Yuster

We present a novel approach for computing all maximum consecutive subsums in a sequence of positive integers in near-linear time. Solutions for this problem over binary sequences can be used for reporting existence of Parikh vectors in a bit string. Recently, several attempts have been made to build indexes for all Parikh vectors of a binary string in subquadratic time. However, no algorithm is known to date which can beat by more than a polylogarithmic factor the naive Θ ( n 2 ) procedure. We show how to construct a ( 1 + ϵ ) -approximate index for all Parikh vectors of a binary string in O ( n log 2 n log ( 1 + ϵ ) ) time, for any constant ϵ > 0. Such index is approximate, in the sense that it leaves a small chance for false positives (no false negatives are possible). However, we can tune the parameters of the algorithm so that we can strictly control such a chance of error while still guaranteeing strong subquadratic running time.

ICML Conference 2014 Conference Paper

Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost

• Ferdinando Cicalese
• Eduardo Sany Laber
• Aline Medeiros Saettler

In several applications of automatic diagnosis and active learning a central problem is the evaluation of a discrete function by adaptively querying the values of its variables until the values read uniquely determine the value of the function. In general reading the value of a variable is done at the expense of some cost (computational or possibly a fee to pay the corresponding experiment). The goal is to design a strategy for evaluating the function incurring little cost (in the worst case or in expectation according to a prior distribution on the possible variables’ assignments). We provide an algorithm that builds a strategy (decision tree) with both expected cost and worst cost which are at most an O(\log n) factor away from, respectively, the minimum possible expected cost and the minimum possible worst cost. Our algorithm provides the best possible approximation simultaneously with respect to both criteria. In fact, there is no algorithm that can guarantee o(\log n) approximation, under the assumption that \cal P ≠\cal NP.

TCS Journal 2014 Journal Article

Latency-bounded target set selection in social networks

• Ferdinando Cicalese
• Gennaro Cordasco
• Luisa Gargano
• Martin Milanič
• Ugo Vaccaro

Motivated by applications in sociology, economy and medicine, we study variants of the Target Set Selection problem, first proposed by Kempe, Kleinberg and Tardos. In our scenario one is given a graph G = ( V, E ), integer values t ( v ) for each vertex v (thresholds), and the objective is to determine a small set of vertices (target set) that activates a given number (or a given subset) of vertices of G within a prescribed number of rounds. The activation process in G proceeds as follows: initially, at round 0, all vertices in the target set are activated; subsequently at each round r ⩾ 1 every vertex of G becomes activated if at least t ( v ) of its neighbors are already active by round r − 1. It is known that the problem of finding a minimum cardinality Target Set that eventually activates the whole graph G is hard to approximate to a factor better than O ( 2 log 1 − ϵ | V | ). In this paper we give exact polynomial time algorithms to find minimum cardinality Target Sets in graphs of bounded clique-width, and exact linear time algorithms for trees.

TCS Journal 2012 Journal Article

The binary identification problem for weighted trees

• Ferdinando Cicalese
• Tobias Jacobs
• Eduardo Laber
• Caio Valentim

The Binary Identification Problem for weighted trees asks for the minimum cost strategy (decision tree) for identifying a vertex in an edge weighted tree via testing edges. Each edge has assigned a different cost, to be paid for testing it. Testing an edge e reveals in which component of T − e lies the vertex to be identified. We give a complete characterization of the computational complexity of this problem with respect to both tree diameter and degree. In particular, we show that it is strongly NP-hard to compute a minimum cost decision tree for weighted trees of diameter at least 6, and for trees having degree three or more. For trees of diameter five or less, we give a polynomial time algorithm. Moreover, for the degree 2 case, we significantly improve the straightforward O ( n 3 ) dynamic programming approach, and provide an O ( n 2 ) time algorithm. Finally, this work contains the first approximate decision tree construction algorithm that breaks the barrier of factor log n.

TCS Journal 2011 Journal Article

On the complexity of searching in trees and partially ordered structures

• Ferdinando Cicalese
• Tobias Jacobs
• Eduardo Laber
• Marco Molinaro

We study the problem of minimizing the weighted average number of queries to identify an initially unknown object in a poset. We show that for general posets, there cannot be any o ( log n ) -approximation algorithm unless NP ⊆ TIME ( n O ( log log n ) ). When the Hasse diagram of the partially ordered set has the structure of a tree, the problem is equivalent to the following tree search problem: in a given rooted tree T = ( V, E ) a node has been marked and we want to identify it. In order to locate the marked node, we can perform node queries. A node query u asks whether the marked node lies in the subtree rooted at u. A function w: V → Z + is given which defines the likelihood for a node to be the one marked, and we want the strategy that minimizes the expected number of queries. Prior to this paper the complexity of this problem had remained open. We prove that the above tree search problem is NP -complete even for the class of trees with diameter at most 4. This results in a complete characterization of the complexity of the problem with respect to the diameter size. In fact, for diameter not larger than 3 we show that the problem is polynomially solvable using a dynamic programming approach. In addition we prove that the problem is NP -complete even for the class of trees of maximum degree at most 16. To the best of our knowledge, the only known result in this direction is that the tree search problem is solvable in O ( | V | log | V | ) time for trees with degree at most 2 (paths). Our results sharply contrast with those for the variant of the problem where one is interested in minimizing the maximum number of queries. In fact, for the worst case scenario, linear time algorithms are known for finding an optimal search strategy [K. Onak, P. Parys, Generalization of binary search: searching in trees and forest-like partial orders, in: FOCS’06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, USA, 2006, pp. 379–388; S. Mozes, K. Onak, O. Weimann, Finding an optimal tree searching strategy in linear time, in: SODA’08: Proceedings of the Nineteenth Annual ACM–SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2008, pp. 1096–1105].

SODA Conference 2006 Conference Paper

On the competitive ratio of evaluating priced functions

• Ferdinando Cicalese
• Eduardo Sany Laber

STOC Conference 2005 Conference Paper

A new strategy for querying priced information

• Ferdinando Cicalese
• Eduardo Sany Laber

This paper focuses on competitive function evaluation in the context of computing with priced information. A function f is given together with a cost c x for each variable x of f. The cost c x has to be paid to read the value of x. The problem is to design algorithms that query the values of the variables sequentially in order to compute the function while trying to minimize the total cost incurred. Competitive analysis is employed to evaluate the performance of the algorithms. We describe a novel approach for devising efficient algorithms in this setting. We apply our approach to several classes of functions which have been studied in the literature of computing with priced information. In all cases considered, our approach provides algorithms that achieve better bounds than the best known algorithm for the same class of functions.More precisely, for the class of monotone boolean functions, we give a polynomial time algorithm with extremal competitiveness (k+l - √ min(k,l)) where k (l) denotes the minimum number of variables that one must read, in the worst case, in order to prove that the function under consideration evaluates to 1 (0). This dramatically improves upon the best known result which is an exponential time 2 max(k, l)-competitive algorithm. For the subclass of monotone boolean functions known as Threshold Trees we further improve our bounds and give a polynomial time algorithm with extremal competitive ratio 1.618 max(k, l).We then apply our methodology to classes of non-boolean functions. We consider the case of the so called Game Trees . We improve upon previously published results for this class of functions providing a polynomial time algorithm with extremal competitive ratio 1.5 γ(f), where γ(f) is a lower bound on the extremal competitive ratio of any deterministic algorithm.Finally, we consider the case when f is the function min (minimum). In this case, we are able to determine the optimal competitiveness for the problem. In fact we provide an algorithm with an (n-2)-competitive ratio, which matches the known lower bound.

TCS Journal 2002 Journal Article

Least adaptive optimal search with unreliable tests

• Ferdinando Cicalese
• Daniele Mundici
• Ugo Vaccaro

We consider the basic problem of searching for an unknown m-bit number by asking the minimum possible number of yes–no questions, when up to a finite number e of the answers may be erroneous. In case the (i+1)th question is adaptively asked after receiving the answer to the ith question, the problem was posed by Ulam and Rényi and is strictly related to Berlekamp's theory of error correcting communication with noiseless feedback. Conversely, in the fully non-adaptive model when all questions are asked before knowing any answer, the problem amounts to finding a shortest e-error correcting code. Let qe(m) be the smallest integer q satisfying Berlekamp’s bound ∑i=0 e( q i )⩽2q−m. Then at least qe(m) questions are necessary, in the adaptive, as well as in the non-adaptive model. In the fully adaptive case, optimal searching strategies using exactly qe(m) questions always exist up to finitely many exceptional m's. At the opposite non-adaptive case, searching strategies with exactly qe(m) questions—or equivalently, e-error correcting codes with 2m codewords of length qe(m)—are rather the exception, already for e=2, and are generally not known to exist for e>2. In this paper, for each e>1 and all sufficiently large m, we exhibit searching strategies that use a first batch of m non-adaptive questions and then, only depending on the answers to these m questions, a second batch of qe(m)−m non-adaptive questions. These strategies are automatically optimal. Since even in the fully adaptive case, qe(m)−1 questions do not suffice to find the unknown number, and qe(m) questions generally do not suffice in the non-adaptive case, the results of our paper provide e fault tolerant searching strategies with minimum adaptiveness and minimum number of tests.

TCS Journal 2000 Journal Article

Optimal strategies against a liar

• Ferdinando Cicalese
• Ugo Vaccaro

We consider the following scenario: There are two individuals, say Q (Questioner) and R (Responder), involved in a search game. Player R chooses a number, say x, from the set S={1, …, M}. Player Q has to find out x by asking questions of type: “which one of the sets A1, A2, …, Aq, does x belong to? ”, where the sets A1, …, Aq constitute a partition of S. Player R answers “i” to indicate that the number x belongs to Ai. We are interested in the least number of questions player Q has to ask in order to be always able to correctly guess the number x, provided that R can lie at most e times. The case e=0 obviously reduces to the classical q-ary search, and the necessary number of questions is [log qM]. The case q=2 and e⩾1 has been widely studied, and it is generally referred to as Ulam's game. In this paper we consider the general case of arbitrary q⩾2. Under the assumption that player R is allowed to lie at most twice throughout the game, we determine the minimum number of questions Q needs to ask in order to successfully search for x in a set of cardinality M=qi, for any i⩾1. As a corollary, we obtain a counterexample to a recently proposed conjecture of Aigner, for the case of an arbitrary number of lies. We also exactly solve the problem when player R is allowed to lie a fixed but otherwise arbitrary number of times e, and M=qi, with i not too large with respect to q. For the general case of arbitrary M, we give fairly tight upper and lower bounds on the number of the necessary questions.