Ahlswede and Winter introduced a Chernoff bound for matrix-valued random variables, which is a non-trivial generalization of the usual Chernoff bound for real-valued random variables. We present an efficient derandomization of their bound using the method of pessimistic estimators (see Raghavan). As a consequence, we derandomize a construction of Alon ... more >>>

more >>>

We continue the study of {\em robust} tensor codes and expand the
class of base codes that can be used as a starting point for the
construction of locally testable codes via robust two-wise tensor
products. In particular, we show that all unique-neighbor expander
codes and all locally correctable codes, ... more >>>

In this note we improve a recent result by Arora, Khot, Kolla, Steurer, Tulsiani, and Vishnoi on solving the Unique Games problem on expanders.

Given a (1 - epsilon)-satisfiable instance of Unique Games with the constraint graph G, our algorithm finds an assignments satisfying at least a (1 - C ... more >>>