Source author record

Avivit Levy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Mind the Gap

We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary $D$ of $d$ patterns, where each pattern contains a special gap symbol that can match any string, so that given a text that arrives online, a character at a time, we can report all of the patterns from $D$ that are suffixes of the text that has arrived so far, before the next character arrives. In more general versions the gap symbols are associated with bounds determining the possible lengths of matching strings. Finding efficient algorithmic solutions for (online) DMOG has proven to be a difficult algorithmic challenge. We demonstrate that the difficulty in obtaining efficient solutions for the DMOG problem even, in the offline setting, can be traced back to the infamous 3SUM conjecture. Interestingly, our reduction deviates from the known reduction paths that follow from 3SUM. In particular, most reductions from 3SUM go through the set-disjointness problem, which corresponds to the problem of preprocessing a graph to answer edge-triangles queries. We use a new path of reductions by considering the complementary, although structurally very different, vertex-triangles queries. Using this new path we show a conditional lower bound of $Ω(δ(G_D)+op)$ time per text character, where $G_D$ is a bipartite graph that captures the structure of $D$ , $δ(G_D)$ is the degeneracy of this graph, and $op$ is the output size. We also provide matching upper-bounds (up to sub-polynomial factors) for the vertex-triangles problem, and then extend these techniques to the online DMOG problem. In particular, we introduce algorithms whose time cost depends linearly on $δ(G_D)$ . Our algorithms make use of graph orientations, together with some additional techniques. Finally, when $δ(G_D)$ is large we are able to obtain even more efficient solutions.

preprint2014arXiv

Dictionary Matching with One Gap

The dictionary matching with gaps problem is to preprocess a dictionary $D$ of $d$ gapped patterns $P_1,\ldots,P_d$ over alphabet $Σ$ , where each gapped pattern $P_i$ is a sequence of subpatterns separated by bounded sequences of don't cares. Then, given a query text $T$ of length $n$ over alphabet $Σ$ , the goal is to output all locations in $T$ in which a pattern $P_i\in D$ , $1\leq i\leq d$ , ends. There is a renewed current interest in the gapped matching problem stemming from cyber security. In this paper we solve the problem where all patterns in the dictionary have one gap with at least $α$ and at most $β$ don't cares, where $α$ and $β$ are given parameters. Specifically, we show that the dictionary matching with a single gap problem can be solved in either $O(d\log d + |D|)$ time and $O(d\log^{\varepsilon} d + |D|)$ space, and query time $O(n(β-α)\log\log d \log ^2 \min \{ d, \log |D| \} + occ)$ , where $occ$ is the number of patterns found, or preprocessing time and space: $O(d^2 + |D|)$ , and query time $O(n(β-α) + occ)$ , where $occ$ is the number of patterns found. As far as we know, this is the best solution for this setting of the problem, where many overlaps may exist in the dictionary.

preprint2014arXiv

Longest Common Subsequence in k-length substrings

In this paper we define a new problem, motivated by computational biology, $LCSk$ aiming at finding the maximal number of $k$ length $substrings$ , matching in both input strings while preserving their order of appearance. The traditional LCS definition is a special case of our problem, where $k = 1$ . We provide an algorithm, solving the general case in $O(n^2)$ time, where $n$ is the length of the input strings, equaling the time required for the special case of $k=1$ . The space requirement of the algorithm is $O(kn)$ . %, however, in order to enable %backtracking of the solution, $O(n^2)$ space is needed. We also define a complementary $EDk$ distance measure and show that $EDk(A,B)$ can be computed in $O(nm)$ time and $O(km)$ space, where $m$ , $n$ are the lengths of the input sequences $A$ and $B$ respectively.

preprint2012arXiv

On Approximating String Selection Problems with Outliers

Many problems in bioinformatics are about finding strings that approximately represent a collection of given strings. We look at more general problems where some input strings can be classified as outliers. The Close to Most Strings problem is, given a set S of same-length strings, and a parameter d, find a string x that maximizes the number of "non-outliers" within Hamming distance d of x. We prove this problem has no PTAS unless ZPP=NP, correcting a decade-old mistake. The Most Strings with Few Bad Columns problem is to find a maximum-size subset of input strings so that the number of non-identical positions is at most k; we show it has no PTAS unless P=NP. We also observe Closest to k Strings has no EPTAS unless W[1]=FPT. In sum, outliers help model problems associated with using biological data, but we show the problem of finding an approximate solution is computationally difficult.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.