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)