85 Result(s)

Article

Double String Tandem Repeats

A tandem repeat is an occurrence of two adjacent identical substrings. In this paper, we introduce the notion of a double string, which consists of two parallel strings, and we study the problem of locating all t...

Amihood Amir, Ayelet Butman, Gad M. Landau, Shoshana Marcus, Dina Sokol in Algorithmica (2023)

Article

Multidimensional Period Recovery

Multidimensional data are widely used in real-life applications. Intel’s new brand of SSDs, called 3D XPoint, is an example of three-dimensional data. Motivated by a structural analysis of multidimensional dat...

Amihood Amir, Ayelet Butman, Eitan Kondratovsky, Avivit Levy, Dina Sokol in Algorithmica (2022)

Chapter and Conference Paper

Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction

We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications, e.g., in computational biolog...

Ramtin Afshar, Amihood Amir… in String Processing and Information Retrieval (2020)

Chapter and Conference Paper

Approximating the Anticover of a String

The k-anticover of a string S is a set of distinct k-length substrings such that every index in S is contained in one of these substrings. The existence of an anticover indicates a lack of structure in S. It was ...

Amihood Amir, Itai Boneh, Eitan Kondratovsky in String Processing and Information Retrieval (2020)

Chapter and Conference Paper

Multidimensional Period Recovery

Multidimensional data are widely used in real-life applications. Intel’s new brand of SSDs, called 3D XPoint, is an example of three-dimensional data. Motivated by a structural analysis of multidimensional dat...

Amihood Amir, Ayelet Butman… in String Processing and Information Retrieval (2020)

Article

Can We Recover the Cover?

Data analysis typically involves error recovery and detection of regularities as two different key tasks. In this paper we show that there are data types for which these two tasks can be powerfully combined. A co...

Amihood Amir, Avivit Levy, Moshe Lewenstein, Ronit Lubin, Benny Porat in Algorithmica (2019)

Article

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 m...

Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat… in Algorithmica (2019)

Chapter and Conference Paper

Finding Periods in Cartesian Tree Matching

In Cartesian tree matching, two strings match if the Cartesian trees of the strings are the same. In this paper we define full, initial, and general periods in Cartesian tree matching, and present an O(n) time al...

Magsarjav Bataa, Sung Gwan Park, Amihood Amir, Gad M. Landau… in Combinatorial Algorithms (2019)

Chapter and Conference Paper

Searching for a Modified Pattern in a Changing Text

Much attention has been devoted recently to the dynamic model of pattern matching. In this model the input is updated or changed locally. One is interested in obtaining the appropriate search result in time th...

Amihood Amir, Eitan Kondratovsky in String Processing and Information Retrieval (2018)

Chapter and Conference Paper

Longest Common Factor After One Edit Operation

It is well known that the longest common factor (LCF) of two strings over an integer alphabet can be computed in time linear in the total length of the two strings. Our aim here is to present an algorithm that...

Amihood Amir, Panagiotis Charalampopoulos… in String Processing and Information Retrieval (2017)

Article

Configurations and Minority in the String Consensus Problem

The Closest String Problem is defined as follows. Let \(S\) S ...

Amihood Amir, Haim Paryenty, Liam Roditty in Algorithmica (2016)

Reference Work Entry In depth

Two-Dimensional Scaled Pattern Matching

Amihood Amir in Encyclopedia of Algorithms (2016)

Reference Work Entry In depth

Similarity Between Compressed Strings

** Wook Kim, Amihood Amir, Gad M. Landau, Kunsoo Park in Encyclopedia of Algorithms (2016)

Reference Work Entry In depth

Multidimensional Compressed Pattern Matching

Amihood Amir in Encyclopedia of Algorithms (2016)

Chapter and Conference Paper

Period Recovery over the Hamming and Edit Distances

A string S of length n has period P of length p if \(S[i]=S[i+p]\) ...

Amihood Amir, Mika Amit, Gad M. Landau, Dina Sokol in LATIN 2016: Theoretical Informatics (2016)

Chapter and Conference Paper

Range LCP Queries Revisited

The Range LCP problem is to preprocess a string \(S[1\dots n]\) , to enable efficient solutions of the following query: given a ...

Amihood Amir, Moshe Lewenstein… in String Processing and Information Retrieval (2015)

Chapter and Conference Paper

On the Hardness of Optimal Vertex Relabeling and Restricted Vertex Relabeling

Vertex Relabeling is a variant of the graph relabeling problem. In this problem, the input is a graph and two vertex labelings, and the question is to determine how close are the labelings. The distance measur...

Amihood Amir, Benny Porat in Combinatorial Pattern Matching (2015)

Chapter and Conference Paper

Multiply Balanced k −Partitioning

The problem of partitioning an edge-capacitated graph on n vertices into k balanced parts has been amply researched. Motivated by applications such as load balancing in distributed systems and market segmentation...

Amihood Amir, Jessica Ficler, Robert Krauthgamer… in LATIN 2014: Theoretical Informatics (2014)