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 Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings
Authors: Petr Kučera, Petr Savický3832-3840
AAAI 2021 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | The main result of our paper is that a PC-BDMC can be compiled into a PC encoding of size polynomial with respect to the total size of the input BDMC. As a consequence, we get that both PC-BDMCs and PC encodings share the same algorithmic properties while being equally succinct. Theorem 1. Let D be a smooth PC-BDMC representing a function f(x). Then we can construct in polynomial time a PC encoding of f(x). Theorem 3. PC-BDMCs (and thus also PC encodings) are strictly more succinct than generalized PC backdoor trees. Proof. For a given n, let us consider three sets of variables: x = {xi,j | i, j {1, . . . , n}}, y = {yi,j,k | i, j {1, . . . , n}, k {1, . . . , n 1}}, and z = {zi,j | i, j {1, . . . , n}}. For every i = 1, . . . , n, we introduce formulas... |
| Researcher Affiliation | Academia | Petr Kuˇcera,1 Petr Savick y2 1 Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University, Czech Republic 2 Institute of Computer Science of the Czech Academy of Sciences, Czech Republic |
| Pseudocode | No | The paper defines logical constructions and presents clauses in Table 1, but it does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any specific links to source code repositories or explicit statements about code availability for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical evaluation on datasets, so there is no mention of publicly available datasets for training. |
| Dataset Splits | No | As a theoretical paper, it does not describe experimental procedures involving dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe experimental procedures that would require specific hardware specifications. |
| Software Dependencies | No | The paper focuses on theoretical concepts and does not list any specific software dependencies with version numbers required for experiments. |
| Experiment Setup | No | The paper is theoretical and does not include details about an experimental setup, such as hyperparameters or training configurations. |