Computational Short Cuts in Infinite Domain Constraint Satisfaction

• URL: http://arxiv.org/abs/2211.10144v1
• Date: Fri, 18 Nov 2022 10:37:51 GMT
• Title: Computational Short Cuts in Infinite Domain Constraint Satisfaction
• Authors: Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak
• Abstract summary: A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a solvable-time class. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have. We introduce sidedoors as an alternative to backdoors.
• Score: 34.522661052004324
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A backdoor in a finite-domain CSP instance is a set of variables where each possible instantiation moves the instance into a polynomial-time solvable class. Backdoors have found many applications in artificial intelligence and elsewhere, and the algorithmic problem of finding such backdoors has consequently been intensively studied. Sioutis and Janhunen (Proc. 42nd German Conference on AI (KI-2019)) have proposed a generalised backdoor concept suitable for infinite-domain CSP instances over binary constraints. We generalise their concept into a large class of CSPs that allow for higher-arity constraints. We show that this kind of infinite-domain backdoors have many of the positive computational properties that finite-domain backdoors have: the associated computational problems are fixed-parameter tractable whenever the underlying constraint language is finite. On the other hand, we show that infinite languages make the problems considerably harder: the general backdoor detection problem is W[2]-hard and fixed-parameter tractability is ruled out under standard complexity-theoretic assumptions. We demonstrate that backdoors may have suboptimal behaviour on binary constraints -- this is detrimental from an AI perspective where binary constraints are predominant in, for instance, spatiotemporal applications. In response to this, we introduce sidedoors as an alternative to backdoors. The fundamental computational problems for sidedoors remain fixed-parameter tractable for finite constraint language (possibly also containing non-binary relations). Moreover, the sidedoor approach has appealing computational properties that sometimes leads to faster algorithms than the backdoor approach.

Related papers

• Tractable Offline Learning of Regular Decision Processes [50.11277112628193]
  This work studies offline Reinforcement Learning (RL) in a class of non-Markovian environments called Regular Decision Processes (RDPs) Ins, the unknown dependency of future observations and rewards from the past interactions can be captured experimentally. Many algorithms first reconstruct this unknown dependency using automata learning techniques.
  arXiv  Detail & Related papers  (2024-09-04T14:26:58Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary. Characterizing the complexity of these problems requires new algorithmic techniques and lower bound methods. We present a unitary property testing-based approach towards an oracle separation between $mathsfQMA$ and $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2022-10-12T03:01:00Z)
• Practical computational advantage from the quantum switch on a generalized family of promise problems [0.0]
  The quantum switch is a quantum computational primitive that provides computational advantage by applying operations in a superposition of orders. In this work, we use Complex Hadamard matrices to introduce more general promise problems.
  arXiv  Detail & Related papers  (2022-07-26T15:57:12Z)
• Constrained mixers for the quantum approximate optimization algorithm [55.41644538483948]
  We present a framework for constructing mixing operators that restrict the evolution to a subspace of the full Hilbert space. We generalize the "XY"-mixer designed to preserve the subspace of "one-hot" states to the general case of subspaces given by a number of computational basis states. Our analysis also leads to valid Trotterizations for "XY"-mixer with fewer CX gates than is known to date.
  arXiv  Detail & Related papers  (2022-03-11T17:19:26Z)
• Constructive Post-Quantum Reductions [18.527533843982905]
  We present positive and negative results for converting large classes of classical reductions to the postquantum setting. We put forth a framework for reductions (or general interaction) with stateful solvers for a computational problem.
  arXiv  Detail & Related papers  (2022-03-04T13:46:34Z)
• Finding Backdoors to Integer Programs: A Monte Carlo Tree Search Framework [22.824450460839245]
  A backdoor is a small subset of an instance's integer variables with the following property. We propose BaMCTS, a Monte Carlo Tree Search framework for finding backdoors to MIPs.
  arXiv  Detail & Related papers  (2021-10-16T00:36:53Z)
• Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
  We formulate novel fast NonLocal blocks, capable of reducing complexity from quadratic to linear with no loss in performance. The proposed method, which we dub as "Poly-NL", is competitive with state-of-the-art performance across image recognition, instance segmentation, and face detection tasks.
  arXiv  Detail & Related papers  (2021-07-06T19:51:37Z)
• Reassessing the computational advantage of quantum-controlled ordering of gates [0.0]
  In quantum computation, indefinite causal structures decide whether two unitary gates commute or anticommute with a single call to each gate. In this work, we show that this advantage is smaller than expected. We present a causal algorithm that solves the only known specific FPP with $O(nlog(n))$ queries and a causal algorithm that solves every FPP with $O(nsqrtn)$ queries.
  arXiv  Detail & Related papers  (2021-02-22T19:00:08Z)
• Combinatorial Pure Exploration with Full-bandit Feedback and Beyond: Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
  When developing an algorithm for optimization, it is commonly assumed that parameters such as edge weights are exactly known as inputs. In this article, we review recently proposed techniques for pure exploration problems with limited feedback.
  arXiv  Detail & Related papers  (2020-12-31T12:40:52Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  A fundamental component of neural network verification is the computation of bounds on the values their outputs can take. We propose a novel approach based on Lagrangian Decomposition. We show that we obtain bounds comparable with off-the-shelf solvers in a fraction of their running time.
  arXiv  Detail & Related papers  (2020-02-24T17:55:10Z)

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.