Title: The Importance of Being Biased
<P>
Muli Safra (TAU)
<P>

ABSTRACT:

<P>
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.

<P>
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.
<P>

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