2026-07-21T19:26:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8349 2024-03-06T10:42:06Z ddc:004 open_access

Fast and Deterministic Constant Factor Approximation Algorithms for LCS Imply New Circuit Lower Bounds Abboud, Amir Rubinstein, Aviad Distributed PCP Longest Common Subsequence Fine-grained Complexity Strong Exponential Time Hypothesis The Longest Common Subsequence (LCS) is one of the most basic similarity measures and it captures important applications in bioinformatics and text analysis. Following the SETH-based nearly-quadratic time lower bounds for LCS from recent years, it is a major open problem to understand the complexity of approximate LCS. In the last ITCS [AB17] drew an interesting connection between this problem and the area of circuit complexity: they proved that approximation algorithms for LCS in deterministic truly-subquadratic time imply new circuit lower bounds (E^NP does not have non-uniform linear-size Valiant Series Parallel circuits). In this work, we strengthen this connection between approximate LCS and circuit complexity by applying the Distributed PCP framework of [ARW17]. We obtain a reduction that holds against much larger approximation factors (super-constant versus 1+o(1)), yields a lower bound for a larger class of circuits (linear-size NC^1), and is also easier to analyze. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amir Abboud and Aviad Rubinstein 2018 Is Part Of LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2018.35 urn:nbn:de:0030-drops-83490 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.35 eng https://creativecommons.org/licenses/by/3.0/legalcode