文章基本信息

标题：Fine-Grained Hardness for Edit Distance to a Fixed Sequence
本地全文：下载
作者：Abboud, Amir ; Vassilevska Williams, Virginia
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：198
DOI：10.4230/LIPIcs.ICALP.2021.7
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：SAT;edit distance;fine-grained complexity;conditional lower bound;sequence alignment