Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers

DOI10.1145/1595391.1595393MaRDI QIDQ2947543zbMATH OpenOpenAlexFDO

Authors Prasad Raghavendra, Venkatesan Guruswami

Publication date 24 September 2015

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1595391.1595393

zbMATH Keywords

hardness of approximationlinearity testingprobabilistically checkable proofssparse linear equations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• A 3-query PCP over integers
• \(\mathcal{NP}\)-hardness of approximately solving linear equations over reals
• NP-hardness of approximately solving linear equations over reals
• On the hardness of approximating max-satisfy
• Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups

Cited in

(3)

• \(\mathcal{NP}\)-hardness of approximately solving linear equations over reals
• A 3-query PCP over integers
• Optimal inapproximability of promise equations over finite groups

This page was built for publication: Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers

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