Distributed PCP theorems for hardness of approximation in P

DOI10.1109/FOCS.2017.12MaRDI QIDQ6946376zbMATH OpenFDO

Authors Aviad Rubinstein, Amir Abboud, Ryan Williams

Publication date 6 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2017.12

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(6)

• Finer-grained reductions in fine-grained hardness of approximation
• The complexity of non-stationary reinforcement learning
• Local proofs approaching the witness length
• Fine-grained hardness for edit distance to a fixed sequence
• Optimal fine-grained hardness of approximation of linear equations
• Exploring the approximability landscape of 3SUM

This page was built for publication: Distributed PCP theorems for hardness of approximation in P

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