Title: Shorter long codes with applications to Unique Games
Speaker: Raghu Meka, Institute of Advanced Study
Date: Wednesday, September 28, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
The long code is a central tool in hardness of approximation, especially in questions related to the unique games conjecture. Many hardness reductions and constructions of integrality gap instances use the long code as a core gadget. However, this is also the source of their inefficiency, as the long code is indeed quite long. Specifically, it has only N codewords but dimension 2^N.
In this work, we show a different code, which we call the ``short code'', that is exponentially more efficient, but still can be used in long code's place in many of these applications, leading to significant quantitative improvements. In particular, we use our code to show instances on which the Arora, Barak, Steurer [ABS10] algorithm for unique games, as well as certain semidefinite hierarchies, require almost exponential time, thus considerably strengthening the known evidence in support of the Unique Games Conjecture. We also use our code to obtain more efficient "alphabet reduction gadgets" for unique games with only a quasipolynomial blowup, as opposed to the previous reduction by Khot, Kindler, Mossel and O'Donnell that had an exponential blowup.
Joint work with Boaz Barak, Parikshit Gopalan, Johan Hastad, Prasad Raghavendra, David Steurer.