Theory of Computing ------------------- Title : Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs Authors : Per Austrin, Subhash Khot, and Muli Safra Volume : 7 Number : 3 Pages : 27-43 URL : https://theoryofcomputing.org/articles/v007a003 Abstract -------- We study the inapproximability of Vertex Cover and Independent Set on degree-d graphs. We prove that: * Vertex Cover is Unique Games-hard to approximate within a factor 2 - (2+o_d(1)) \log\log d / \log d. This exactly matches the algorithmic result of Halperin (SICOMP'02) up to the o_d(1) term. * Independent Set is Unique Games-hard to approximate within a factor O(d / \log^2 d). This improves the d / \log^{O(1)}(d) Unique Games-hardness result of Samorodnitsky and Trevisan (STOC'06). Additionally, our result does not rely on the construction of a query efficient PCP.