Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > UNIQUE GAMES, LOCALLY TESTABLE CODES:
Reports tagged with Unique Games, Locally Testable Codes:
TR11-142 | 2nd November 2011
Boaz Barak, Parikshit Gopalan, Johan Hastad, Raghu Meka, Prasad Raghavendra, David Steurer

Making the long code shorter, with applications to the Unique Games Conjecture

Revisions: 1

The long code is a central tool in hardness of approximation, especially in
questions related to the unique games conjecture. We construct a new code that
is exponentially more ecient, but can still be used in many of these applications.
Using the new code we obtain exponential improvements over several ... more >>>




ISSN 1433-8092 | Imprint