Lower Bounds and Faster Algorithms for Equality Constraints
Authors: Peter Jonsson, Victor Lagerkvist
IJCAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the fine-grained complexity of NPcomplete, infinite-domain constraint satisfaction problems (CSPs) parameterised by a set of firstorder definable relations (with equality). Such CSPs are of central importance since they form a subclass of any infinite-domain CSP parameterised by a set of first-order definable relations. We prove that under the randomised exponential-time hypothesis it is not possible to find c > 1 such that a CSP over an arbitrary finite equality language is solvable in O(cn) time (n is the number of variables). |
| Researcher Affiliation | Academia | Peter Jonsson and Victor Lagerkvist Department of Computer and Information Science, Link oping University, Link oping, Sweden {peter.jonsson, victor.lagerkvist}@liu.se |
| Pseudocode | Yes | Consider the following algorithm A(I) for an instance I of CSP(Γ). 1. Let I = (V, C) and let V = {x1, . . . , xn}. 2. Define s: V {1, . . . , n} such that s(xi) = i. 3. If s is a solution to I, then return yes . |
| Open Source Code | No | The paper does not provide any concrete access information for source code, such as a repository link or an explicit statement of code release. |
| Open Datasets | No | The paper does not mention the use of any datasets for training or evaluation, as it is theoretical in nature. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical validation on datasets, therefore no dataset split information is provided. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for experiments or computations. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not detail an experimental setup, hyperparameters, or training configurations. |