### Abstract

In 1997, Håstad showed NP-hardness of (1 - ε,1/q + δ)-approximating Max-3Lin(ℤ_{q}); however it was not until 2007 that Guruswami and Raghavendra were able to show NP-hardness of (1 - ε,δ)-approximating Max-3Lin(ℤ). In 2004, Khot-Kindler-Mossel- O'Donnell showed UG-hardness of (1 - ε,δ)-approximating Max-2Lin(ℤ_{q}) for q = q(ε,δ) a sufficiently large constant; however achieving the same hardness for Max-2Lin(ℤ) was given as an open problem in Raghavendra's 2009 thesis. In this work we show that fairly simple modifications to the proofs of the Max-3Lin(ℤ_{q}) and Max-2Lin(ℤ_{q}) results yield optimal hardness results over ℤ. In fact, we show a kind of "bicriteria" hardness: even when there is a (1 - ε)-good solution over ℤ, it is hard for an algorithm to find a δ-good solution over ℤ, ℤ, or ℤ_{m} for any m ≥ q(ε, δ) of the algorithm's choosing.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011 |

Pages | 23-33 |

Number of pages | 11 |

DOIs | |

State | Published - Aug 29 2011 |

Externally published | Yes |

Event | 26th Annual IEEE Conference on Computational Complexity, CCC 2011 - San Jose, CA, United States Duration: Jun 8 2011 → Jun 10 2011 |

### Publication series

Name | Proceedings of the Annual IEEE Conference on Computational Complexity |
---|---|

ISSN (Print) | 1093-0159 |

### Other

Other | 26th Annual IEEE Conference on Computational Complexity, CCC 2011 |
---|---|

Country | United States |

City | San Jose, CA |

Period | 6/8/11 → 6/10/11 |

### ASJC Scopus subject areas

- Software
- Theoretical Computer Science
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Hardness of Max-2Lin and Max-3Lin over integers, reals, and large cyclic groups'. Together they form a unique fingerprint.

## Cite this

*Proceedings - 26th Annual IEEE Conference on Computational Complexity, CCC 2011*(pp. 23-33). [5959818] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2011.37