%0 Journal Article %1 Hastad/01 %A H\aastad, Johan %C New York, NY, USA %D 2001 %I ACM %J J. ACM %K PCP approximation complexity %N 4 %P 798--859 %R http://doi.acm.org/10.1145/502090.502098 %T Some optimal inapproximability results %U http://portal.acm.org/citation.cfm?doid=502090.502098 %V 48 %X We prove optimal, up to an arbitrary ε > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.

@article{Hastad/01, abstract = {We prove optimal, up to an arbitrary ε > 0, inapproximability results for Max-E k-Sat for k ≥ 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and Set Splitting. As a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. In particular, for Max-E2-Sat, Max-Cut, Max-di-Cut, and Vertex cover.}, added-at = {2008-07-09T22:26:18.000+0200}, address = {New York, NY, USA}, author = {H{\aa}stad, Johan}, biburl = {https://www.bibsonomy.org/bibtex/207048e1944dd1e24e2094d143cccd206/mboley}, description = {Some optimal inapproximability results}, doi = {http://doi.acm.org/10.1145/502090.502098}, interhash = {9398b38ff683c6ac7aed6f507427f4b5}, intrahash = {07048e1944dd1e24e2094d143cccd206}, issn = {0004-5411}, journal = {J. ACM}, keywords = {PCP approximation complexity}, number = 4, pages = {798--859}, publisher = {ACM}, timestamp = {2008-07-09T22:56:32.000+0200}, title = {Some optimal inapproximability results}, url = {http://portal.acm.org/citation.cfm?doid=502090.502098}, volume = 48, year = 2001 }