4.5k citations
- Tel Aviv UniversityIL181 papers
- Boston UniversityUS130 papers
- Weizmann Institute of ScienceIL117 papers
- Ariel UniversityIL101 papers
- Ben-Gurion University of the NegevIL99 papers
- Centre National de la Recherche ScientifiqueFR98 papers
- Hebrew University of JerusalemIL95 papers
- Technion – Israel Institute of TechnologyIL90 papers
- Massachusetts Institute of TechnologyUS82 papers
- Stanford UniversityUS75 papers
- University of CambridgeGB70 papers
- University of Maryland, College ParkUS68 papers
5 papers · 2 filters
Pattern Matching under Polynomial Transformation
Ayelet Butman, Peter Clifford, Raphael Clifford +5
We consider a class of pattern matching problems where a normalising transformation is applied at every alignment. Normalised pattern matching plays a key role in fields as diverse…
A Linear Time Algorithm for Seeds Computation
Tomasz Kociumaka, Marcin Kubica, Jakub Radoszewski +2
A seed in a word is a relaxed version of a period in which the occurrences of the repeating subword may overlap. We show a linear-time algorithm computing a linear-size representat…
Space Lower Bounds for Online Pattern Matching
Raphael Clifford, Markus Jalsenius, Ely Porat +1
We present space lower bounds for online pattern matching under a number of different distance measures. Given a pattern of length m and a text that arrives one character at a time…
Minimum Weight Cycles and Triangles: Equivalences and Algorithms
Liam Roditty, Virginia Vassilevska Williams
We consider the fundamental algorithmic problem of finding a cycle of minimum weight in a weighted graph. In particular, we show that the minimum weight cycle problem in an undirec…
A cuckoo hashing variant with improved memory utilization and insertion time
Ely Porat, Bar Shalem
Cuckoo hashing [4] is a multiple choice hashing scheme in which each item can be placed in multiple locations, and collisions are resolved by moving items to their alternative loca…