Nicola Prezza

Ruben Becker, Davide Cenzato, Travis Gagie et al.

The suffix tree is arguably the most fundamental data structure on strings: introduced by Weiner (SWAT 1973) and McCreight (JACM 1976), it allows solving a myriad of computational problems on strings in linear time. Motivated by its large space usage, subsequent research focused first on reducing its size by a constant factor via Suffix Arrays, and later on reaching space proportional to the size of the compressed string. Modern compressed indexes, such as the $r$-index (Gagie et al., SODA 2018), fit in space proportional to $r$, the number of runs in the Burrows-Wheeler transform (a strong and universal repetitiveness measure). These advances, however, came with a price: while modern compressed indexes boast optimal bounds in the RAM model, they are often orders of magnitude slower than uncompressed counterparts in practice due to catastrophic cache locality. This reality gap highlights that Big-O complexity in the RAM model has become a misleading predictor of real-world performance, leaving a critical question unanswered: can we design compressed indexes that are efficient in the I/O model of computation? We answer this in the affirmative by introducing a new Suffix Array sampling technique based on particular path decompositions of the suffix tree. We prove that sorting the suffix tree leaves by specific priority functions induces a decomposition where the number of distinct paths (each corresponding to a string suffix) is bounded by $r$. This allows us to solve indexed pattern matching efficiently in the I/O model using a Suffix Array sample of size at most $r$, strictly improving upon the (tight) $2r$ bound of Suffixient Arrays, another recent compressed Suffix Array sampling technique.

Stefano Calzavara, Lorenzo Cazzaro, Giulio Ermanno Pibiri et al.

Verifying the robustness of machine learning models against evasion attacks at test time is an important research problem. Unfortunately, prior work established that this problem is NP-hard for decision tree ensembles, hence bound to be intractable for specific inputs. In this paper, we identify a restricted class of decision tree ensembles, called large-spread ensembles, which admit a security verification algorithm running in polynomial time. We then propose a new approach called verifiable learning, which advocates the training of such restricted model classes which are amenable for efficient verification. We show the benefits of this idea by designing a new training algorithm that automatically learns a large-spread decision tree ensemble from labelled data, thus enabling its security verification in polynomial time. Experimental results on public datasets confirm that large-spread ensembles trained using our algorithm can be verified in a matter of seconds, using standard commercial hardware. Moreover, large-spread ensembles are more robust than traditional ensembles against evasion attacks, at the cost of an acceptable loss of accuracy in the non-adversarial setting.

Giovanna D'Agostino, Nicola Cotumaccio, Alberto Policriti et al.

The states of a deterministic finite automaton A can be identified with collections of words in Pf(L(A)) -- the set of prefixes of words belonging to the regular language accepted by A. But words can be ordered and among the many possible orders a very natural one is the co-lexicographic one. Such naturalness stems from the fact that it suggests a transfer of the order from words to the automaton's states. In a number of papers automata admitting a total ordering of states coherent with the ordering of the set of words reaching them have been proposed. Such class of ordered automata -- the Wheeler automata -- turned out to be efficiently stored/searched using an index. Unfortunately not all automata can be totally ordered as previously outlined. However, automata can always be partially ordered and an intrinsic measure of their complexity can be defined and effectively determined, as the minimum width of one of their admissible partial orders. As shown in previous works, this new concept of width of an automaton has useful consequences in the fields of graph compression, indexing data structures, and automata theory. In this paper we prove that a canonical, minimum-width, partially-ordered automaton accepting a language L -- dubbed the Hasse automaton H of L -- can be exhibited. H provides, in a precise sense, the best possible way to (partially) order the states of any automaton accepting L, as long as we want to maintain an operational link with the (co-lexicographic) order of Pf(L(A)). Using H we prove that the width of the language can be effectively computed from the minimum automaton recognizing the language. Finally, we explore the relationship between two (often conflicting) objectives: minimizing the width and minimizing the number of states of an automaton.