Conditional Lower Bounds for Longest Common Subsequence
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Proves conditional lower bounds for Longest Common Subsequence under SETH-based reductions by reducing Orthogonal Vectors into fine-grained parameter settings; defines seven parameters (N, M, L, deletions, matching pairs, dominant pairs, alphabet) and lists complete parameter relations, then constructs padded hard instances to realize each setting. Shows the classic DP barrier is essentially tight, gives N + M^2 tight up to logs for many regimes, and pinpoints a binary alphabet gives new algorithm — the first polynomial-factor improvement since 1990.
AI-written summary · about