inapproximability

Volume 3, Article 6 (pages 103-128)
Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
by David Zuckerman
Volume 3, Article 3 (pages 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy
by Ishay Haviv, Oded Regev, and Amnon Ta-Shma
Volume 1, Article 7 (pages 119-148)
Query Efficient PCPs with Perfect Completeness
by Johan Håstad and Subhash Khot