Metadata about: This thesis investigates the extent to which the optimal value of a constraint satisfaction problem (CSP) can be approximated by some sentence of fixed point logic with counting (FPC). It is known that, assuming $/mathsf{P} /neq /mathsf{NP}$ and the Unique Games Conjecture, the best polynomial time approximation algorithm for any CSP is given by solving and rounding a specific semidefinite programming relaxation. We prove an analogue of this result for algorithms that are definable as FPC-interpretations, which holds without the assumption that $/mathsf{P} /neq /mathsf{NP}$. While we are not able to drop (an FPC-version of) the Unique Games Conjecture as an assumption, we do present some partial results toward proving it. Specifically, we give a novel construction which shows that, for all $/alpha>0$, there exists a positive integer $q = /text{poly}(/frac{1}{/alpha})$ such that no there is no FPC-interpretation giving an $/alpha$-approximation of Unique Games on a label set of size $q$.

About: This thesis investigates the extent to which the optimal value of a constraint satisfaction problem (CSP) can be approximated by some sentence of fixed point logic with counting (FPC). It is known that, assuming $/mathsf{P} /neq /mathsf{NP}$ and the Unique Games Conjecture, the best polynomial time approximation algorithm for any CSP is given by solving and rounding a specific semidefinite programming relaxation. We prove an analogue of this result for algorithms that are definable as FPC-interpretations, which holds without the assumption that $/mathsf{P} /neq /mathsf{NP}$. While we are not able to drop (an FPC-version of) the Unique Games Conjecture as an assumption, we do present some partial results toward proving it. Specifically, we give a novel construction which shows that, for all $/alpha>0$, there exists a positive integer $q = /text{poly}(/frac{1}{/alpha})$ such that no there is no FPC-interpretation giving an $/alpha$-approximation of Unique Games on a label set of size $q$.

an Entity references as follows:

Graph IRI	Count
http://ns.inria.fr/covid19/graph/entityfishing	9
http://ns.inria.fr/covid19/graph/articles	3

Faceted Search & Find service v1.13.91

This work is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License.
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Copyright © 2009-2025 OpenLink Software