Approximability and inapproximability of fundamental problems

This thesis contains three papers on approximation algorithms and inapproximability results. Paper A contains NP-hardness inapproximability results for the Max-2Lin(2) problem, where 2Lin(2) refers to a system of linear equations modulo $2$ with two variables per equation. Paper B gives an approximation algorithm for the recently introduced linearly ordered hypergraph coloring problem. Before our paper, the best known approximation algorithm was able to color a $2$-colorable $3$-uniform hypergraph with $n$ nodes using $O(\sqrt[5]n)$ colors. But our approximation algorithm is able to do it in only $\log_2(n)$ colors, breaking the $n^{O(1)}$ barrier. Paper C introduces two completely new concepts called promise useful and promise useless for Promise Constraint Satisfaction Problems (PCSPs). The paper also contains a survey of essential results related to these two concepts. The hope is that these concepts will lead to a new direction of research for PCSPs.