English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We consider the following string matching problem on a node-labeled graph$G=(V,E)$: given a pattern string $P$, decide whether there exists a path in$G$ whose concatenation of node labels equals $P$. This is a basic primitive invarious problems in bioinformatics, graph databases, or networks. The hardnessresults of Backurs and Indyk (FOCS 2016) imply that this problem cannot besolved in better than $O(|E||P|)$ time, under the Orthogonal Vectors Hypothesis(OVH), and this holds even under various restrictions on the graph (Equi etal., ICALP 2019).  In this paper we consider its offline version, namely the one in which we areallowed to index the graph in order to support time-efficient string matchingqueries. Indeed, it was tantalizing in the string matching community to believethat sub-quadratic time queries can be achieved, e.g. at the cost of ahigh-degree polynomial-time indexing.  We disprove this belief, showing that, under OVH, no polynomial-time indexcan support querying $P$ in time $O(|E|^\delta|P|^\beta)$, with either $\delta< 1$ or $\beta < 1$. We prove this tight bound employing a knownself-reducibility technique, e.g. from the field of dynamic algorithms, whichtranslates conditional lower bounds for an online problem to its offlineversion.  As a side-contribution, we formalize this technique with the notion of linearindependent-components reduction, allowing for a simple proof of our result. Asanother illustration of our technique, we also translate the quadraticconditional lower bound of Backurs and Indyk (STOC 2015) for the problem ofmatching a query string inside a text, under edit distance. We obtain ananalogous tight quadratic lower bound for its offline version, improving therecent result of Cohen-Addad, Feuilloley and Starikovskaya (SODA 2019), butwith a slightly different boundary condition.

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