activity
20182022
most citedEfficient average-case population recovery in the presence of insertions and deletions

4 citations · 7 across the 6 of their papers we have counts for

collaborators
Showing 2021Show all

2 papers · 1 filter

cs.DS2021

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…

cs.DS2021

Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces

Xi Chen, Anindya De, Chin Ho Lee +2

In the standard trace reconstruction problem, the goal is to \emph{exactly} reconstruct an unknown source string from independent "traces", which are cop…