NP-hardness of approximately solving linear equations over reals
From MaRDI portal
Publication:5419111
DOI10.1145/1993636.1993692zbMath1288.68271OpenAlexW1992771184MaRDI QIDQ5419111
Subhash A. Khot, Dana Moshkovitz
Publication date: 5 June 2014
Published in: Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/1721.1/63152
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Linear equations (linear algebraic aspects) (15A06)