[talks] ​Yonatan Naaman will present his Pre FPO "Hardness from Dense Subgraph Conjectures" on Thursday, May 25th, 2017 in CS 402 at 6pm.

[Nicki Gotsis]

Yonatan Naaman will present his Pre FPO "Hardness from Dense Subgraph Conjectures" on Thursday, May 25th, 2017 in CS 402 at 6pm.

Everyone is invited to attend his talk.  

The members of his committee are as follows:
Moses Charikar (adviser)
Sanjeev Arora (reader) 
Anthony Wirth (U. Melbourne) (reader) 
Mark Braverman (non-reader) 
Matt Weinberg (non-reader) 

Title: "Hardness from Dense Subgraph Conjectures".

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 objective 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 hypotheticals. One class of conjectures focuses on the approximability of the Densest k-Subgraph (DkS) problem. Namely, the conjectured hardness of both adversarial 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 thesis, we describe techniques for proving stronger hardness results conditioned on both the known and the conjectured hardness of Densest k-Subgraph. We show how previous results on DkS imply stronger lower bounds on ``MinRep-hard'' problems, as well as a simple technique for converting many proofs of MinRep-hardness into proofs of DkS-hardness. Using this and other techniques, we show DkS hardness for problems such as Minimum Colored Cut, Target Set Selection, Minimum Monotone Satisfying Assignment (MMSA), Network Flow Interdiction, Power Dominating Set, Densest k-Common Subgraph, among others. In the case of Target Set Selection and MMSA, we show how to obtain substantially stronger lower bounds by exploiting the self-similar structure of instances conjectured to be average-case-hard. We also provide improved approximation algorithms for some of the discussed problems.