Fine-grained complexity meets IP = PSPACE

DOI10.1137/1.9781611975482.1MaRDI QIDQ5236182zbMATH OpenOpenAlexFDO

Authors Lijie Chen, Kaifeng Lyu, Guy N. Rothblum, Aviad Rubinstein, Shafi Goldwasser

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.02351

Mathematics Subject Classification ID

Data structures (68P05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: In this paper we study the fine-grained complexity of finding exact and approximate solutions to problems in P. Our main contribution is showing reductions from exact to approximate solution for a host of such problems. As one (notable) example, we show that the Closest-LCS-Pair problem (Given two sets of strings $A$ and $B$, compute exactly the maximum $extsfLCS(a,b)$ with $(a,b)inAimesB$) is equivalent to its approximation version (under near-linear time reductions, and with a constant approximation factor). More generally, we identify a class of problems, which we call BP-Pair-Class, comprising both exact and approximate solutions, and show that they are all equivalent under near-linear time reductions. Exploring this class and its properties, we also show: $$ Under the NC-SETH assumption (a significantly more relaxed assumption than SETH), solving any of the problems in this class requires essentially quadratic time. $$ Modest improvements on the running time of known algorithms (shaving log factors) would imply that NEXP is not in non-uniform $extsf{NC}^1$. $$ Finally, we leverage our techniques to show new barriers for deterministic approximation algorithms for LCS. At the heart of these new results is a deep connection between interactive proof systems for bounded-space computations and the fine-grained complexity of exact and approximate solutions to problems in P. In particular, our results build on the proof techniques from the classical IP = PSPACE result.

Recommendations

• Towards hardness of approximation for polynomial time problems
• Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
• On some fine-grained questions in algorithms and complexity
• Simulating branching programs with edit distance and friends: or: a polylog shaved is a lower bound made
• Multivariate fine-grained complexity of longest common subsequence

Cited in

(10)

• Towards hardness of approximation for polynomial time problems
• Classical algorithms from quantum and Arthur-Merlin communication protocols
• Probabilistically checkable arguments for all NP
• Finer-grained reductions in fine-grained hardness of approximation
• Approximation algorithms for LCS and LIS with truly improved running times
• Local proofs approaching the witness length
• Fine-grained hardness for edit distance to a fixed sequence
• Improved approximation for longest common subsequence over small alphabets
• Optimal fine-grained hardness of approximation of linear equations
• Streaming and small space approximation algorithms for edit distance and longest common subsequence

This page was built for publication: Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236182)