NP-hardness of approximately solving linear equations over reals

DOI10.1137/110846415MaRDI QIDQ2848199zbMATH OpenOpenAlexFDO

Authors Subhash Khot, Dana Moshkovitz

Publication date 25 September 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/110846415

zbMATH Keywords

hardness of approximationlinear equationsPCP

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• NP-hardness of approximately solving linear equations over reals
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• On the hardness of approximating max-satisfy
• On the hardness of approximating balanced homogenous 3-Lin
• Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers

Cited in

(6)

• Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers
• scientific article; zbMATH DE number 6823767 (Why is no real title available?)
• On the hardness of approximating balanced homogenous 3-Lin
• NP-hardness of approximately solving linear equations over reals
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Optimal inapproximability of promise equations over finite groups

This page was built for publication: \(\mathcal{NP}\)-hardness of approximately solving linear equations over reals

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