Yonatan Naamad will present his FPO, "Hardness from Densest Subgraph Conjectures"on Monday, October 30, 2017 at 4pm in CS 402. The members of his committee are: Moses Charikar (adviser); Readers: Sanjeev Arora and Anthony Wirth (University of Melbourne); Examiners: Moses Charikar, Mark Braverman, and Matt Weinberg. A copy of his thesis is available in Room 310. Everyone is invited to attend his talk. The talk abstract follows below. ABSTRACT: Karp's seminal paper on NP-Completeness provided computer scientists with a toolkit for showing computational hardness, conditioned on a complexity theoretic conjecture, for a wide variety of optimization problems. However, the techniques used in his paper say little about the hardness of approximating the optimal objec­tive values of these problems. While researchers have since managed to find tight bounds on the approximability of some of these NP-hard problems, many others still have embarrassingly large gaps between their known upper and lower limits of approximation. To fill in these gaps, researchers have posed myriad new complexity theoretic conjectures that entail stronger lower bounds at the expense of more demanding hy­potheticals. One class of conjectures focuses on the approximability of the DENSEST k-SUBGRAPH (DkS) problem. Namely, the conjectured hardness of both adversar­ial and average-case variants of DkS has been shown to imply stronger hardness for many problems for which good approximation algorithms have proven elusive. In this dissertation, we study a variety of problems, each of which can have their hardness tied back to that of DENSEST k-SUBGRAPH. We describe techniques for proving stronger hardness results conditioned on both the known and the conjectured hardness of DkS. We show how previous results on DkS imply stronger lower bounds on "MIN-REP-hard" problems, as well as a simple technique for converting many proofs of MIN-REP-hardness into proofs of DkS-hardness. Using this and other tech­niques, we show DkS hardness for problems such as TARGET SET SELECTION, MIN­IMUM MONOTONE SATISFYING ASSIGNMENT, MIN-COST COLORED CUT, NET­WORK FLOW INTERDICTION, and DENSEST k-COMMON SUBGRAPH, among others. In the case of TARGET SET SELECTION and MINIMUM MONOTONE SATISFYING ASSIGNMENT, we show how to obtain substantially stronger lower bounds by exploit­ing the self-similar structure of instances conjectured to be average-case-hard. We introduce the MIDDLEBOX ROUTING-class of problems, and show show exact, ap­proximation, and hardness results for its member problems. We provide an 0( ,vn) approximation algorithm for Mk U, and discuss both approximation and hardness results for DENSEST COMMON SUBGRAPH variants.