SDDs Are Exponentially More Succinct than OBDDs
Authors: Simone Bova
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that SDDs are more succinct than OBDDs also in theory, by constructing a family of boolean functions where each member has polynomial SDD size but exponential OBDD size. |
| Researcher Affiliation | Academia | Simone Bova Technische Universit at Wien Favoritenstraße 9 11 1040 Wien (Austria) |
| Pseudocode | No | The paper contains mathematical definitions, propositions, theorems, and proofs, but no structured pseudocode or algorithm blocks are provided. |
| Open Source Code | No | The paper does not provide any statement or link for open-source code related to the described methodology. |
| Open Datasets | No | This is a theoretical paper that does not involve empirical evaluation on datasets. |
| Dataset Splits | No | This is a theoretical paper that does not involve empirical evaluation on datasets, thus no dataset split information is provided. |
| Hardware Specification | No | The paper describes theoretical proofs and constructions, and does not report on empirical experiments requiring hardware specifications. |
| Software Dependencies | No | The paper describes theoretical proofs and constructions, and does not report on empirical experiments requiring specific software dependencies. |
| Experiment Setup | No | This is a theoretical paper focused on proofs and constructions, and does not include details about an experimental setup or hyperparameters. |