Hardness for Sequence Problems - LCS and Frechet Distance
summary
Reduction from Orthogonal Vectors produces two sequences X,Y of length N·poly(d) (construction time N·poly(d)) so LCS, edit distance, DTW and Fréchet are distinguishing β vs β+1 hard: if some vector pair is orthogonal the optimal score increases by one, otherwise it stays at N·β. The reduction uses tiny coordinate gadgets (C0=46, C1=4, E0=6 4, E1=6), concatenated into q/r/p padding blocks with N−1 repeats to force gadget-aligned matches, yielding no n^{2−ε} algorithm unless OV fails.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:18Plan and scope
- 1:44Sequence walk problems
- 3:28Frechet distance
- 7:51Dynamic time warping
- 8:54Longest common subsequence
- 12:14Edit distance
- 15:22Hardness introduction
- 17:38OV conjecture and bounds
- 20:52Reduction strategy
- 24:24LCS reduction attempt
- 28:41Gadgets for LCS
- 32:20Final LCS construction
- 36:10Vector gadgets construction
- 40:29Coordinate gadgets
- 45:35Hardness recap
- 49:33Conclusions and Q&A
related talks
10mQuery, Communication and Discrepancy
23mTowards General and Tight Hardness Results for Graph Problems
19mDeterministic Dynamic Matching In Worst-Case Update Time
30mLocal Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
28mCommunication Avoiding Algorithms for Linear Algebra and Beyond
31mNear-Optimal Distributed Implementations of Dynamic Algorithms for Symmetry Breaking Problems
20mCounting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems