This dissertation continues the line of work that develops techniques to show inapproximability results for these problems. In the process, we provide hardness of approximation results for the following problems. - Problems Between P and NP: Dense Constraint Satisfaction Problems (CSPs), Densest k-Subgraph with Perfect Completeness, VC Dimension, and Littlestone's Dimension. - Parameterized Problems: k-Dominating Set, k-Clique, k-Biclique, Densest k-Subgraph, Parameterized 2-CSPs, Directed Steiner Network, k-Even Set, and k-Shortest Vector. - Problems in P: Closest Pair, and Maximum Inner Product.
Some of our results, such as those for Densest k-Subgraph, Directed Steiner Network and Parameterized 2-CSP, also present the best known inapproximability factors for the problems, even in the (believed) NP-hard regime. Furthermore, our results for k-Dominating Set and k-Even Set resolve two long-standing open questions in the field of parameterized complexity.