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].
Graph Width Measures for CNF-Encodings with Auxiliary Variables
Authors: Stefan Mengel, Romain Wallon
JAIR 2020 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We make two main contributions on the expressivity of bounded width CNF-formulas here. As a first main contribution, we show, for a wide class of width measures, that one can give width lower bounds of any encoding of a function by means of communication complexity (Theorem 9). ... In a second main contribution, we focus on the relative expressive power of different graph width measures for clausal encodings... the commonly considered width notions are all up to constant factors equivalent to either primal treewidth or to incidence cliquewidth (Theorem 23). |
| Researcher Affiliation | Academia | Stefan Mengel EMAIL Romain Wallon EMAIL CRIL, CNRS & Univ Artois Rue Jean Souvraz SP18 62300 Lens, France |
| Pseudocode | No | The paper describes theoretical proofs and constructions but does not include any structured pseudocode or algorithm blocks. Methods are described narratively within the text, such as the construction of F' in the proof of Theorem 13. |
| Open Source Code | No | The paper does not provide any explicit statements about releasing source code for the described methodology, nor does it include links to code repositories. |
| Open Datasets | No | The paper focuses on theoretical properties of CNF-encodings and mathematical functions (e.g., At Most One_n-function, PERM_n function, cardinality constraints) rather than empirical evaluation on specific datasets. Therefore, it does not provide information about public or open datasets. |
| Dataset Splits | No | The paper presents theoretical research and does not involve empirical experiments requiring dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any experimental setup that would require hardware specifications. The mention of GPUs in the conclusion refers to work by other researchers. |
| Software Dependencies | No | The paper focuses on theoretical contributions and does not present any experimental implementation details that would require listing specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is purely theoretical and does not include any experimental setup details, hyperparameters, or training configurations. |