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

DOI10.1145/2751322zbMATH Open1347.68173OpenAlexW2221384962MaRDI QIDQ2828232FDOQ2828232

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

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?

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)

Cited In (3)

• A 3-query PCP over integers
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Title not available (Why is that?)

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)