Approximability and inapproximability of fundamental problems
Time: Fri 2025-09-12 15.15
Location: D3, Lindstedtvägen 5
Language: English
Subject area: Mathematics
Doctoral student: Björn Martinsson , Algebra, kombinatorik och topologi
Opponent: Assistant Professor Jakub Opršal, University of Birmingham
Supervisor: Johan Håstad, Matematik (Avd.); Per Austrin, Teoretisk datalogi, TCS
QC 2025-08-21
Abstract
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.