Computer Science/Discrete Mathematics Seminar II

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. In the first talk (of the two talk series) I will focus on the particular application of our short code to construct a graph in which small subsets of vertices have very strong expansion (''small set expander'') and the number of large eigenvalues is large. This will illustrate the main ideas in our constructions and their applications. In the second talk I will focus on obtaining a derandomized version of the Majority is Stablest result of Mossel, O'Donnell and Oleszkiewicz for Reed-Muller codes. This, along with the above ''small set expansion'' property, help us carry over most of the previous applications of the long code in relation to unique games to the short code. Joint work with Boaz Barak, Parikshit Gopalan, Johan Hastad, Prasad Raghavendra, David Steurer and with David Zuckerman.