Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups

DOI10.1145/2751322zbMath1347.68173OpenAlexW2221384962MaRDI QIDQ2828232

Yi Wu, Ryan O'Donnell, 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)

Related Items (1)

Unnamed Item

This page was built for publication: Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups