Abstract
We indicate strong non-Approximability factors for central problems: N1/4 for Max Clique; N1/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.