Learnability of Solutions to Conjunctive Queries
Authors: Hubie Chen, Matthew Valeriote
JMLR 2019 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This article completes the classification program towards which this progression of results strived, by presenting a negative learnability result that complements the mentioned positive learnability result. In addition, a further negative learnability result is exhibited, which indicates a dichotomy within the problems to which the first negative result applies. In order to obtain our negative results, we make use of universal-algebraic concepts. Keywords: concept learning, computational learning theory, dichotomy theorems, reductions, universal algebra |
| Researcher Affiliation | Academia | Hubie Chen EMAIL Birkbeck, University of London, London WC1E 7HX, United Kingdom Matthew Valeriote EMAIL Department of Mathematics & Statistics, Mc Master University, Hamilton, Canada |
| Pseudocode | No | The paper describes algorithms and reductions in prose, for example, in Section 3.1 Oracular pwm-reducibility and throughout Section 5, but does not present any explicitly labeled 'Pseudocode' or 'Algorithm' blocks. |
| Open Source Code | No | The paper does not contain any explicit statements about releasing source code for the described methodology, nor does it provide links to any code repositories. The license information provided is for the paper itself, not for code. |
| Open Datasets | No | The paper discusses relational structures like B3SAT, BHORN 3SAT, and VF as theoretical examples for its analysis, but these are abstract mathematical constructs and not empirical datasets that would require public access information. |
| Dataset Splits | No | The paper focuses on theoretical learnability results using abstract relational structures and does not conduct experiments involving empirical datasets, therefore, no dataset splits are discussed or provided. |
| Hardware Specification | No | The paper presents theoretical results and proofs in computational learning theory and universal algebra. It does not describe any experimental setup or computational experiments that would require specific hardware specifications. |
| Software Dependencies | No | The paper is theoretical in nature, focusing on learnability and algebraic concepts. It does not describe any computational implementation or experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is a theoretical work presenting proofs and dichotomy theorems related to learnability problems. It does not involve practical experiments, training models, or hyperparameter tuning, and thus provides no experimental setup details. |