Backdoor Decomposable Monotone Circuits and Propagation Complete Encodings
Authors: Petr Kučera, Petr Savický3832-3840
AAAI 2021 | Conference PDF | Archive PDF | Plain Text | 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. |