Improved Non-Approximability Results

We indicate strong non-approximability factors for central problems: N 1=4 for Max Clique; N 1=10 for Chromatic Number; and 66=65 for Max 3SAT. Underlying the Max Clique result is a proof system in which the verifier examines only three "free bits" to attain an error of 1=2. Underlying the Chromatic Number result is a reduction from Max Clique which is more efficient than previous ones