4 citations · 10 across the 11 of their papers we have counts for
11 papers · 1 filter
Sublinear Time Algorithms and Complexity of Approximate Maximum Matching
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
Sublinear time algorithms for approximating maximum matching size have long been studied. Much of the progress over the last two decades on this problem has been on the algorithmic…
Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
Binghui Peng, Aviad Rubinstein
Dynamic algorithms come in three main flavors: (insertions-only), (deletions-only), or (both inser…
Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond -Approximation
Aviad Rubinstein, Junyao Zhao
In this work we give two new algorithms that use similar techniques for (non-monotone) submodular function maximization subject to a cardinality constraint. The first is an offline…
Does Preprocessing help in Fast Sequence Comparisons?
Elazar Goldenberg, Aviad Rubinstein, Barna Saha
We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed…
A Simple Sublinear Algorithm for Gap Edit Distance
Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
We study the problem of estimating the edit distance between two -character strings. While exact computation in the worst case is believed to require near-quadratic time, previo…
Asymmetric Streaming Algorithms for Edit Distance and LCS
Alireza Farhadi, MohammadTaghi Hajiaghayi, Aviad Rubinstein +1
The edit distance (ED) and longest common subsequence (LCS) are two fundamental problems which quantify how similar two strings are to one another. In this paper, we consider these…