4 papers
Approximating the Longest Common Subsequence problem within a sub-polynomial factor in linear time
Negev Shekel Nosatzki
The Longest Common Subsequence (LCS) of two strings is a fundamental string similarity measure with a classical dynamic programming solution taking quadratic time. Despite signific…
Estimating the Longest Increasing Subsequence in Nearly Optimal Time
Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha +1
Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length can be computed exactly i…
Edit Distance in Near-Linear Time: it's a Constant Factor
Alexandr Andoni, Negev Shekel Nosatzki
We present an algorithm for approximating the edit distance between two strings of length in time up to a constant factor, for any . Our resu…
Two Party Distribution Testing: Communication and Security
Alexandr Andoni, Tal Malkin, Negev Shekel Nosatzki
We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have samples from, re…