An Algorithmic Bridge Between Hamming and Levenshtein Distances
summary
Presents a 1+ε approximation algorithm for the new EDa metric (substitution cost 1/a, indel cost 1) that runs sublinearly for realistic parameters: overall time ≈ n/(a·ε) + a·k^3, so for example a = n^{1/4} and k < n^{1/4} yields sublinear time. Key tools are approximate LCEd queries built by sampling rate 1/d with O(n/d) preprocessing and ~O(d·k) query cost, plus reductions from exact EDa via granularity 1/a; matching conditional lower bounds show the exact algorithm is essentially tight.
AI-written summary · about
chapters (5)
related talks
01h 02mFine-Grained Counting Complexity I
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
01h 01mExact Algorithms from FPT Algorithms
32mCompetitive Data Structure Dynamization
34mTesting Intersectingness of Uniform Families or how Dana and I intersected
33mLower Bounds for Subexponential Parameterized Complexity of Minimum Fill-in and Related Problems
30mParameterized Inapproximability of Max k-Subset Intersection under ETH