Massimo Equi

STOC Conference 2025 Conference Paper

Distributed Quantum Advantage for Local Problems

• Alkida Balliu
• Sebastian Brandt 0002
• Xavier Coiteux-Roy
• Francesco d'Amore 0001
• Massimo Equi
• François Le Gall
• Henrik Lievonen
• Augusto Modanese

TCS Journal 2024 Journal Article

Elastic founder graphs improved and enhanced

• Nicola Rizzo
• Massimo Equi
• Tuukka Norri
• Veli Mäkinen

Indexing labeled graphs for pattern matching is a central challenge of pangenomics. Equi et al. (2022) [14] developed the Elastic Founder Graph (EFG) representing an alignment of m sequences of length n, drawn from alphabet Σ plus the special gap character: the paths spell the original sequences or their recombination. By enforcing the semi-repeat-free property, the EFG admits a polynomial-space index for linear-time pattern matching, breaking through the conditional lower bounds on indexing labeled graphs (Equi et al. [13]). In this work, we improve the space of the EFG index answering pattern matching queries in linear time, from linear in the length of all strings spelled by three consecutive node labels, to linear in the size of the edge labels. Then, we develop linear-time construction algorithms optimizing for different metrics: we improve the existing linearithmic construction algorithms to O ( m n ), by solving the novel exclusive ancestor set problem on trees; we propose, for the simplified gapless setting, an O ( m n ) -time solution minimizing the maximum block height, that we generalize by substituting block height with prefix-aware height. Finally, to show the versatility of the framework, we develop a BWT-based EFG index and study how to encode and perform document listing queries on a set of paths of the graphs, reporting which paths present a given pattern as a substring. We propose the EFG framework as an improved and enhanced version of the framework for the gapless setting, along with construction methods that are valid in any setting concerned with the segmentation of aligned sequences.

TCS Journal 2023 Journal Article

Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

• Massimo Equi
• Veli Mäkinen
• Alexandru I. Tomescu

The string matching problem on a node-labeled graph G = ( V, E ) asks whether a given pattern string P equals the concatenation of node labels of some path in G. This is a basic primitive in various problems in bioinformatics, graph databases, or networks, and it was recently proven that solving it in time O ( | E | 1 − ϵ | P | ) or O ( | E | | P | 1 − ϵ ) is hard under OVH, the Orthogonal Vectors Hypothesis, and thus under SETH, the Strong Exponential Time Hypothesis (Equi et al. , 2019 [11]). We consider its indexed version, where the graph is indexed to support string queries. We show that, under OVH, no polynomial-time index of the graph performed in time O ( | E | α ) can support querying P in time O ( | P | + | E | δ | P | β ), with either δ < 1 or β < 1. We present our techniques as a general framework, introducing the notion of linear independent-components (lic) reduction, from which we derive our result. This allows us to also translate the quadratic conditional lower bound of Backurs and Indyk (2015) [48] for the problem of matching a query string inside a text, under edit distance, into an analogous tight quadratic lower bound for its indexed version. This improves the recent result of Cohen-Addad, Feuilloley and Starikovskaya (2019) [49], with a slightly different boundary condition. We also apply our technique to obtain the first quadratic indexing lower bounds for Fréchet distance and rooted unlabeled subtree-isomorphism queries.