Dissertation Talk: Approximation and Hardness: Beyond P and NP

Seminar: Dissertation Talk: CS | May 7 | 2-3 p.m. | 310 Soda Hall

 Pasin Manurangsi, University of California, Berkeley

 Electrical Engineering and Computer Sciences (EECS)

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 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 regime that is believed to be NP-hard. Furthermore, our results for k-Dominating Set and k-Even Set resolves two long-standing open questions in the field of parameterized complexity.

Advisors: Prof. Luca Trevisan and Prof. Prasad Raghavendra

 pasin@berkeley.edu, 617-676-8390