Opendata, web and dolomites


Modern Pattern Matching

Total Cost €


EC-Contrib. €






Project "MPM" data sheet

The following table provides information about the project.


Organization address
postcode: 52900

contact info
title: n.a.
name: n.a.
surname: n.a.
function: n.a.
email: n.a.
telephone: n.a.
fax: n.a.

 Coordinator Country Israel [IL]
 Total cost 1˙994˙609 €
 EC max contribution 1˙994˙609 € (100%)
 Programme 1. H2020-EU.1.1. (EXCELLENT SCIENCE - European Research Council (ERC))
 Code Call ERC-2015-CoG
 Funding Scheme ERC-COG
 Starting year 2017
 Duration (year-month-day) from 2017-07-01   to  2022-06-30


Take a look of project's partnership.

# participants  country  role  EC contrib. [€] 
1    BAR ILAN UNIVERSITY IL (RAMAT GAN) coordinator 1˙994˙609.00


 Project objective

The advances in technology over the last decade and the massive amount of data passing through the internet has intrigued and challenged computer scientists, as the old models of computation used before this era are now less relevant or too slow. New computational models have been suggested to tackle these technological advances. In the most basic sense, these modern models allow one to scan the input only once, possible with small auxiliary memory. Nevertheless, modern techniques have also been introduced such as sparse recovery which has proven to be a very useful tool for dealing with modern challenges, and the very popular notion of conditional lower bounds which has provided evidence of hardness for various algorithmic tasks based on very popular conjectures.

Pattern matching plays a crucial role in many computing applications that can be seen in day to day life. However, its research community has only recently started gaining insight on what can be done in modern models, and is lagging behind in this respect. In particular, there are no algorithms for pattern matching problems that have utilized ideas from sparse recovery, and only recently has there been progress in proving conditional lower bounds for string problems. Furthermore, conditional lower bounds suffer from the lack of hardness conjectures which address time/space tradeoffs.

This proposal will close this gap for many important pattern matching problems within the new models of computation, and will be the first to utilize modern algorithmic techniques, such as sparse recovery, and adapting them into the pattern matching world. Furthermore, this proposal will focus on developing a theory for proving conditional time/space lower bounds, based on new hardness conjectures. This will greatly influence not only the pattern matching sub-field, but the entire algorithmic field at large.


year authors and title journal last update
List of publications.
2018 Kopelowitz, Tsvi ; Porat, Ely
A Simple Algorithm for Approximating the Text-To-Pattern Hamming Distance
published pages: , ISSN: , DOI: 10.4230/oasics.sosa.2018.10
1st Symposium on Simplicity in Algorithms (SOSA 2018) 2019-03-27

Are you the coordinator (or a participant) of this project? Plaese send me more information about the "MPM" project.

For instance: the website url (it has not provided by EU-opendata yet), the logo, a more detailed description of the project (in plain text as a rtf file or a word file), some pictures (as picture files, not embedded into any word file), twitter account, linkedin page, etc.

Send me an  email ( and I put them in your project's page as son as possible.

Thanks. And then put a link of this page into your project's website.

The information about "MPM" are provided by the European Opendata Portal: CORDIS opendata.

More projects from the same programme (H2020-EU.1.1.)

NanoPD_P (2020)

High throughput multiplexed trace-analyte screening for diagnostics applications

Read More  

FICOMOL (2019)

Field Control of Cold Molecular Collisions

Read More  

SPA4AstroQIT (2019)

Broadband Quantum-Limited Parametric Amplifier for Astronomy and Quantum Information Technology

Read More