Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups

DOI10.1145/2751322MaRDI QIDQ2828232zbMATH OpenOpenAlexFDO

Authors Ryan O'Donnell, Yi Wu, Yuan Zhou

Publication date 24 October 2016

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

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.206.3877

zbMATH Keywords

hardness of approximationunique games conjecturelarge alphabet setsMAX-2LinMAX-3Lin

Mathematics Subject Classification ID

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

Recommendations

• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 6823767
• Improved NP-inapproximability for 2-variable linear equations
• On the hardness of approximating balanced homogenous 3-Lin
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

Cited in

(4)

• Hardness of solving sparse overdetermined linear systems: a 3-query PCP over integers
• On the hardness of pricing loss-leaders
• A 3-query PCP over integers
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques

This page was built for publication: Hardness of MAX-2Lin and MAX-3Lin over integers, reals, and large cyclic groups

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