NP-hardness of approximately solving linear equations over reals

DOI10.1137/110846415zbMATH Open1272.68144OpenAlexW1991143034MaRDI QIDQ2848199FDOQ2848199

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

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

zbMATH Keywords

linear equationshardness of approximationPCP

Mathematics Subject Classification ID

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

Cited In (4)

• Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers
• On the hardness of approximating balanced homogenous 3-Lin
• Pseudorandom sets in Grassmann graph have near-perfect expansion
• Title not available (Why is that?)

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)