Locally testable codes (LTCs) are error-correcting codes for which membership, in the code, of a given word can be tested by examining it in very few locations. Most known constructions of locally testable codes are linear codes, and give error-correcting codes
whose duals have (superlinearly) {\em many} small weight ... more >>>

In this paper we demonstrate a close connection between UniqueGames and
MultiCut.
%
In MultiCut, one is given a ``network graph'' and a ``demand
graph'' on the same vertex set and the goal is to remove as few
edges from the network graph as ... more >>>

In this paper we will be concerned with a large class of packing
and covering problems which includes Vertex Cover and Independent Set.
Typically, for NP-hard problems among them, one can write an LP relaxation and
then round the solution. For instance, for Vertex Cover, one can obtain a
more >>>