Abboud, Amir ;
Backurs, Arturs
Towards Hardness of Approximation for Polynomial Time Problems
Abstract
Proving hardness of approximation is a major challenge in the field of finegrained complexity and conditional lower bounds in P.
How well can the Longest Common Subsequence (LCS) or the Edit Distance be approximated by an algorithm that runs in nearlinear time?
In this paper, we make progress towards answering these questions.
We introduce a framework that exhibits barriers for truly subquadratic and deterministic algorithms with good approximation guarantees.
Our framework highlights a novel connection between deterministic approximation algorithms for natural problems in P and circuit lower bounds.
In particular, we discover a curious connection of the following form:
if there exists a \delta>0 such that for all \eps>0 there is a deterministic (1+\eps)approximation algorithm for LCS on two sequences of length n over an alphabet of size n^{o(1)} that runs in O(n^{2\delta}) time, then a certain plausible hypothesis is refuted, and the class E^NP does not have nonuniform linear size Valiant SeriesParallel circuits.
Thus, designing a "truly subquadratic PTAS" for LCS is as hard as resolving an old open question in complexity theory.
BibTeX  Entry
@InProceedings{abboud_et_al:LIPIcs:2017:8144,
author = {Amir Abboud and Arturs Backurs},
title = {{Towards Hardness of Approximation for Polynomial Time Problems}},
booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)},
pages = {11:111:26},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770293},
ISSN = {18688969},
year = {2017},
volume = {67},
editor = {Christos H. Papadimitriou},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8144},
URN = {urn:nbn:de:0030drops81443},
doi = {10.4230/LIPIcs.ITCS.2017.11},
annote = {Keywords: LCS, Edit Distance, Hardness in P}
}
28.11.2017
Keywords: 

LCS, Edit Distance, Hardness in P 
Seminar: 

8th Innovations in Theoretical Computer Science Conference (ITCS 2017)

Issue date: 

2017 
Date of publication: 

28.11.2017 