2026-07-30T23:03:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14076 2024-03-06T10:53:24Z ddc:004 open_access

Fine-Grained Hardness for Edit Distance to a Fixed Sequence Abboud, Amir Vassilevska Williams, Virginia SAT edit distance fine-grained complexity conditional lower bound sequence alignment Nearly all quadratic lower bounds conditioned on the Strong Exponential Time Hypothesis (SETH) start by reducing k-SAT to the Orthogonal Vectors (OV) problem: Given two sets A,B of n binary vectors, decide if there is an orthogonal pair a ∈ A, b ∈ B. In this paper, we give an alternative reduction in which the set A does not depend on the input to k-SAT; thus, the quadratic lower bound for OV holds even if one of the sets is fixed in advance. Using the reductions in the literature from OV to other problems such as computing similarity measures on strings, we get hardness results of a stronger kind: there is a family of sequences {S_n}_{n = 1}^{∞}, |S_n| = n such that computing the Edit Distance between an input sequence X of length n and the (fixed) sequence S_n requires n^{2-o(1)} time under SETH. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amir Abboud and Virginia Vassilevska Williams 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.7 urn:nbn:de:0030-drops-140768 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.7 eng https://creativecommons.org/licenses/by/4.0/legalcode