Quadratic-Time Barriers from Self-Referential SAT

arXiv:2611.07308 · cs.DS · Submitted 2026-11-05 · Read on arXiv

cs.DS

Submitted: 2026-11-05

Updated: 2026-11-05

License: http://creativecommons.org/licenses/by/4.0/

The gist: Under the self-referential K-SAT exhaustive-search hypothesis (SRK-ESH), no uniform deterministic algorithm computes exact longest common subsequence or standard edit distance on binary strings in…

Terminology

Abstract

Under the self-referential K-SAT exhaustive-search hypothesis (SRK-ESH), no uniform deterministic algorithm computes exact longest common subsequence or standard edit distance on binary strings in O(n 2-η) time for any fixed η>0, where n is the longer sequence length. The same exclusion holds for one-dimensional dynamic time warping on 0,1,2,4,8 with absolute-difference cost and for five-symbol dynamic time warping with the discrete metric. We derive Orthogonal Vectors hardness in polylogarithmic dimension by splitting the variables of the logarithmic-width source formula into two halves. Existing sequence reductions have polynomial overhead in the dimension. Their output lengths and construction times allow a fixed saving in the target exponent to yield a fixed proportional saving in the source exponent.

Sources

Related papers