Pasin Manurangsi

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2019-49

May 16, 2019

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-49.pdf

The theory of NP-hardness of approximation has led to numerous tight characterizations of approximability of hard combinatorial optimization problems. Nonetheless, there are many fundamental problems which are out of reach for these techniques, such as problems that can be solved (or approximated) in quasi-polynomial time, parameterized problems and problems in P.

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.

Advisors: Luca Trevisan and Prasad Raghavendra

---

BibTeX citation:

@phdthesis{Manurangsi:EECS-2019-49,
    Author= {Manurangsi, Pasin},
    Title= {Approximation and Hardness: Beyond P and NP},
    School= {EECS Department, University of California, Berkeley},
    Year= {2019},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-49.html},
    Number= {UCB/EECS-2019-49},
    Abstract= {The theory of NP-hardness of approximation has led to numerous tight characterizations of approximability of hard combinatorial optimization problems. Nonetheless, there are many fundamental problems which are out of reach for these techniques, such as problems that can be solved (or approximated) in quasi-polynomial time, parameterized problems and problems in P.

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.},
}

EndNote citation:

%0 Thesis
%A Manurangsi, Pasin 
%T Approximation and Hardness: Beyond P and NP
%I EECS Department, University of California, Berkeley
%D 2019
%8 May 16
%@ UCB/EECS-2019-49
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2019/EECS-2019-49.html
%F Manurangsi:EECS-2019-49