Title: The Importance of Being Biased

Muli Safra (TAU)


We show the Vertex-Cover problem to be NP-hard to approximate to within a factor of 1.36 (>4/3). This improves on Hastad's long-standing previous best hardness result for a factor of 7/6.

We introduce, for that purpose, the Biased Long-Code, and utilize techniques regarding the influence of variables on Boolean functions and Erdos-Ko-Rado theorems.

Joint work with Irit Dinur (a former student at TAU -- now at the Institute for Advanced Studies)