Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Computational Short Cuts in Infinite Domain Constraint Satisfaction
Authors: Peter Jonsson, Victor Lagerkvist, Sebastian Ordyniak
JAIR 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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. |
| Researcher Affiliation | Academia | Department of Computer and Information Science Link oping University, Link oping, Sweden; School of Computing, University of Leeds, Leeds, UK |
| Pseudocode | Yes | Figure 2: Algorithm for sidedoor evaluation. (The algorithm block is explicitly labeled as 'algorithm A((V, C), S)') |
| Open Source Code | No | The paper does not provide any statement about releasing its own source code, nor does it provide a link to a code repository for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments with specific datasets. It discusses abstract structures and constraint languages like 'Allen s interval algebra' and 'RCC-5' as examples of theoretical constructs. |
| Dataset Splits | No | The paper does not involve empirical studies or the use of specific datasets, and therefore no dataset splits are mentioned or provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup or the hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and does not describe any experimental setup. Therefore, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and focuses on computational complexity and algorithmic design. It does not contain any experimental setup details such as hyperparameters or system-level training settings. |