Conference paper
Randomness-efficient oblivious sampling
Mihir Bellare, John Rompel
FOCS 1994
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.
Mihir Bellare, John Rompel
FOCS 1994
Ronitt Rubinfeld, Madhu Sudan
SIAM Journal on Computing
Allan Borodin, Jon Kleinberg, et al.
Journal of the ACM
Mihir Bellare, David Cash, et al.
CCS 2011