Professor Amihood Amir is affiliated to the Department of Computer Science, Bar Ilan University, where Amir is currently working as Professor. Amir has numerous publications within the specialty and published in reputed national and international peer-reviewed journals. Amir is actively associated with different national and international societies and academies. Amir gains recognition among the honourable subject experts with the contributions made. Amir has been appreciated by several reputed awards and funding support. Amir major research interest is in studies related to multidimensional pattern matching as applied to text processing, computer vision and multimedia, computational biology.

Having grown accustomed to the presence of all the web data at our fingertips, it is easy to forget that a mere 25 years ago, an encyclopedia on a CD was the height of information technology. At the root of efficient access of this staggering amount of data is indexing. The concept of indexing is that one spends time and effort pre-processing the entire data and constructing auxiliary data structures that will make it possible to efficiently answer future queries of the form: “does input instance I appear in our data?”. Efficient indexing algorithms exist for exact textual retrieval. However, there is crucial need for indexing approximate matching under various distance metrics. Almost no such efficient indexing exists.In this talk we describe an exploration of the complexity of indexing. We consider some very similar basic problems whose matching complexity is linear. These problems are blockmass indexing, histogram indexing, difference indexing, and product indexing. Surprisingly, some of these problems have a different indexing complexity. Moreover, we show that the histogram indexing problem, which has recently been very actively researched, is unlikely to have efficient indexing, since it is 3−SUM hard.