24 citations · 145 across the 45 of their papers we have counts for
50 papers · 1 filter
Set Parameterized Matching via Multi-Layer Hashing
Moshe Lewenstein, Ely Porat
We study the "set parameterized matching" problem, a generalization of the classical parameterized matching problem introduced by Baker. In set parameterized matching, both the pat…
An Improved Algorithm for The -Dyck Edit Distance Problem
Dvir Fried, Shay Golan, Tomasz Kociumaka +3
A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses is the smallest…
Incremental Edge Orientation in Forests
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul +2
For any forest it is possible to orient the edges so that no vertex in has out-degree greater than . This paper considers the incremental edge-orientation p…
Small space and streaming pattern matching with k edits
Tomasz Kociumaka, Ely Porat, Tatiana Starikovskaya
In this work, we revisit the fundamental and well-studied problem of approximate pattern matching under edit distance. Given an integer , a pattern of length , and a text…
Support Optimality and Adaptive Cuckoo Filters
Tsvi Kopelowitz, Samuel McCauley, Ely Porat
Filters (such as Bloom Filters) are data structures that speed up network routing and measurement operations by storing a compressed representation of a set. Filters are space effi…
Improved Circular -Mismatch Sketches
Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz +2
The shift distance between two strings and of the same length is defined as the minimum Hamming distance between and any rotation (cyclic s…