Research map / Graph learning / Knowledge and temporal graphs
An And-Sum Circuit with Signed Edges That Is More Succinct than SDD
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces structured Decomposable And-Sum Circuits (st-DASCs), which replace OR nodes with signed-edge sum nodes so logical negation is poly-time, and shows they are more succinct than st-d-DNNFs (hence SDDs) while supporting SDD's knowledge-compilation-map operations.
Problem
Existing knowledge compilation languages trade off succinctness against tractability: st-d-DNNFs are more succinct than SDDs but lack operations such as logical negation, bounded disjunction and single forgetting that SDDs support.
Approach
Replace OR nodes with sum nodes whose edges carry signs in {-1,1} and AND nodes with min/product semantics, so that negation is a constant-size transformation (a + node with a -1 edge and a constant 1); the resulting structured decomposable circuit is shown to be more succinct than st-d-DNNF and to support SDD's polytime operations.
Key results
- st-DASCs support negation, bounded disjunction, and single forgetting in polynomial time, which st-d-DNNFs do not support.
- st-DASCs are more succinct than st-d-DNNFs: there is a Boolean function with polynomial-size st-DASC whose negation needs super-polynomial st-d-DNNF size (quasi-polynomial separation, n^{Omega~(log n)}).
- ∧C, ∨C and forgetting of a variable set (FO) cannot be done in polynomial time on st-DASCs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace deterministic OR nodes with signed sum nodes and add signed edges | st-DASC · Boolean function representations; comparison with st-d-DNNF | succinctness | Helped |
| Add signed edges to enable logical negation | st-DASC · Knowledge compilation map operations; comparison with SDD | tractable operation support | Helped |
Surprising findings
- Conjunction of multiple formulas (∧C), disjunction of multiple formulas (∨C) and multi-variable forgetting remain intractable for st-DASCs despite the added negation support.
Limitations
- Separation between st-d-DNNF and st-DASC is only quasi-polynomial, not exponential.
- Boolean programming (weighted max-sum query) is not known to be tractable on st-DASCs, unlike st-d-DNNFs.
- Compilation algorithms for st-DASCs are not developed; only an encoding from st-d-DNNFs is given.
Experimental setup
Baselines: SDD st-d-DNNF OBDD d-DNNF
Builds on: st-d-DNNF SDD knowledge compilation map
Closest papers by meaning
- Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs (AAAI 2025 · similarity 0.88)
- A Compiler for Weak Decomposable Negation Normal Form (AAAI 2024 · similarity 0.87)
- New Compilation Languages Based on Restricted Weak Decomposability (AAAI 2025 · similarity 0.87)
- Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates (NeurIPS 2025 · similarity 0.87)
- A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.85)
- A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.