Barna Saha
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 4 in the filters
on a stage with
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Sublinear Time Algorithms for Estimating Edit Distance | Sublinear Algorithms Boot Camp 2024 | 2024-05-21 |
Distinguishes edit distance ≤k from >k^2 in sublinear time and gives concrete algorithms and limits: an adaptive route uses longest common extension queries… | ||
| Approximating Edit Distance in the Fully Dynamic Model | Dynamic Graphs and Algorithm Design (Simons Institute, 2023) | 2023-09-18 |
Presents a dynamic algorithm that approximates edit distance with amortized update time n^ε (for any ε>0) at a polylog(n) approximation factor, trading off… | ||
| An Algorithmic Bridge Between Hamming and Levenshtein Distances | ITCS 2023 | 2023-01-10 |
Presents a 1+ε approximation algorithm for the new EDa metric (substitution cost 1/a, indel cost 1) that runs sublinearly for realistic parameters: overall… | ||
| Playing with Grammars: What Have We Known So Far! | Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) | 2015-12-08 |
Simple randomized stack algorithm gives an O(D) approximation for Dyck edit distance by deleting mismatches (analysis maps to a gambler’s‑ruin walk); refining… | ||
| nothing matches | ||