CSPs with Few Alien Constraints
- URL: http://arxiv.org/abs/2408.12909v2
- Date: Tue, 27 Aug 2024 14:26:53 GMT
- Title: CSPs with Few Alien Constraints
- Authors: Peter Jonsson, Victor Lagerkvist, George Osipov,
- Abstract summary: We consider CSP$(mathcalA cup mathcalB)$ where $mathcalA$ is a structure and $mathcalB$ is an alien structure.
We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts.
- Score: 12.330326247154968
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The constraint satisfaction problem asks to decide if a set of constraints over a relational structure $\mathcal{A}$ is satisfiable (CSP$(\mathcal{A})$). We consider CSP$(\mathcal{A} \cup \mathcal{B})$ where $\mathcal{A}$ is a structure and $\mathcal{B}$ is an alien structure, and analyse its (parameterized) complexity when at most $k$ alien constraints are allowed. We establish connections and obtain transferable complexity results to several well-studied problems that previously escaped classification attempts. Our novel approach, utilizing logical and algebraic methods, yields an FPT versus pNP dichotomy for arbitrary finite structures and sharper dichotomies for Boolean structures and first-order reducts of $(\mathbb{N},=)$ (equality CSPs), together with many partial results for general $\omega$-categorical structures.
Related papers
- A Theory of Interpretable Approximations [61.90216959710842]
We study the idea of approximating a target concept $c$ by a small aggregation of concepts from some base class $mathcalH$.
For any given pair of $mathcalH$ and $c$, exactly one of these cases holds: (i) $c$ cannot be approximated by $mathcalH$ with arbitrary accuracy.
We show that, in the case of interpretable approximations, even a slightly nontrivial a-priori guarantee on the complexity of approximations implies approximations with constant (distribution-free and accuracy-
arXiv Detail & Related papers (2024-06-15T06:43:45Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$.
We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
arXiv Detail & Related papers (2023-02-13T22:51:07Z) - A Newton-CG based barrier-augmented Lagrangian method for general nonconvex conic optimization [53.044526424637866]
In this paper we consider finding an approximate second-order stationary point (SOSP) that minimizes a twice different subject general non conic optimization.
In particular, we propose a Newton-CG based-augmentedconjugate method for finding an approximate SOSP.
arXiv Detail & Related papers (2023-01-10T20:43:29Z) - Merging Ontologies Algebraically [1.6404357211482503]
We show that aligning and merging operations share some generic properties, e.g., idempotence, comativity, and representativity, labeled by (I), (C), (A), and (R)
We also show that the merging system given by $V$-alignment satisfies the properties: (I), (C), (A), and (R)
arXiv Detail & Related papers (2022-08-18T08:57:58Z) - A Ihara-Bass Formula for Non-Boolean Matrices and Strong Refutations of
Random CSPs [4.023424709659175]
We prove strong refutations of random constraint satisfaction problems with $k$ variables per constraints (k-CSPs)
For a random k-CSP instance constructed out of a constraint that is satisfied by a $p$ fraction of assignments, we can efficiently compute a certificate that the optimum satisfies at most a $p+O_k(epsilon)$ fraction of constraints.
arXiv Detail & Related papers (2022-04-20T16:21:21Z) - Local approximation of operators [0.0]
We study the problem of determining the degree of approximation of a non-linear operator between metric spaces $mathfrakX$ and $mathfrakY$.
We establish constructive methods to do this efficiently, i.e., with the constants involved in the estimates on the approximation on $mathbbSd$ being $mathcalO(d1/6)$.
arXiv Detail & Related papers (2022-02-13T19:28:34Z) - On Classifying Continuous Constraint Satisfaction Problems [1.2277343096128712]
A continuous constraint satisfaction problem (CCSP) is a constraint satisfaction problem (CSP) with an interval domain $U subset behavedmathbbR$.
We classify CCSPs that are complete of the Existential Theory of the Reals, i.e., ER-complete.
We show that CCSPs with any one well-behaved curved equality constraint ($f(x,y) geq 0$ and $g(x,y) geq 0$) imply ER-completeness on the class of such CCSPs.
arXiv Detail & Related papers (2021-06-04T10:23:48Z) - On the state space structure of tripartite quantum systems [0.22741525908374005]
It has been shown that the set of states separable across all the three bipartitions [say $mathcalBint(ABC)$] is a strict subset of the set of states having positive partial transposition (PPT) across the three bipartite cuts [say $mathcalPint(ABC)$]
The claim is proved by constructing state belonging to the set $mathPint(ABC)$ but not belonging to $mathcalBint(ABC)$.
arXiv Detail & Related papers (2021-04-14T16:06:58Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
We prove that for every decision tree, the absolute values of the Fourier coefficients of a given order $ellsqrtbinomdell (1+log n)ell-1,$ sum to at most $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, and $c>0$ is an absolute constant.
arXiv Detail & Related papers (2020-08-24T06:50:57Z) - Private Learning of Halfspaces: Simplifying the Construction and
Reducing the Sample Complexity [63.29100726064574]
We present a differentially private learner for halfspaces over a finite grid $G$ in $mathbbRd$ with sample complexity $approx d2.5cdot 2log*|G|$.
The building block for our learner is a new differentially private algorithm for approximately solving the linear feasibility problem.
arXiv Detail & Related papers (2020-04-16T16:12:10Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
We study the fixed-support Wasserstein barycenter problem (FS-WBP)
We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
arXiv Detail & Related papers (2020-02-12T03:40:52Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.