New Directions in Inapproximability: Promise Constraint Satisfaction Problems and Beyond

The field of hardness of approximation has seen a lot of progress in the past three decades resulting in almost optimal inapproximability results for many computational problems, including all Constraint Satisfaction Problems(CSPs). However, our understanding of inapproximability is still rather limited for some fundamental problems such as approximate graph coloring, and problems for which approximation algorithms have been widely studied, for example, clustering, packing, and scheduling problems. In this thesis, we make progress on these questions by studying Promise CSPs that generalize CSPs, and more abstractly, computational problems with a given promise, either a solution satisfying a strong property, or a structural guarantee on the underlying instance. 

Promise Constraint Satisfaction Problems (PCSPs) generalize the traditional CSPs by allowing for a weaker and stronger form for each predicate. PCSPs have received a lot of attention recently, both on the algorithmic and hardness front, and their study has led to breakthroughs in approximate graph and hypergraph coloring problems. In this thesis, we continue that line of work, obtaining new characterization of polynomial time solvability for several classes of Promise CSPs including Boolean monotone PCSPs, variants of graph and hypergraph colorings. We also study robust algorithms for Promise CSPs, and give a dichotomy result characterizing when certain classes of PCSPs have robust algorithms. More generally, we study combinatorial problems under a given structural promise – for example, set cover on set systems where every pair of sets intersect in at most one element. We use inapproximability results on such structured instances to resolve the approximability of multidimensional packing problems and scheduling with communication delays.