Research map / Learning theory and algorithms / Matrix and tensor methods
Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs
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.
The paper treats tensor trains as Boolean function representations, proves they are more succinct than OBDDs while supporting the same polytime operations, placing them in the knowledge compilation map.
Problem
Whether tensor decomposition, specifically tensor trains, can serve as a Boolean function representation that is compared with NNF subsets (e.g., OBDDs) on succinctness and polytime tractable operations in the knowledge compilation map.
Approach
Defines tensor trains with ternary entries as Boolean function representations with variable order, shows an OBDD-to-tensor-train transformation via level-wise smooth OBDDs giving polynomial size, uses the hidden-weighted-bit function for an exponential separation, and proves tractability of the OBDD-equivalent query and transformation set.
Key results
- Tensor trains (TT_<) are shown to be at least as succinct as OBDD_< via a polynomial transformation from OBDD to tensor train, and strictly more succinct using the hidden-weighted-bit function (rank 2n tensor train of size O(n^2) vs OBDD size Omega(2^{0.2n})).
- CO, VA, EQ, SE, CT, conjunction/disjunction bounded compilation, negation, and singleton forgetting are polytime on TT_<, matching OBDD_<.
- Conjunction/disjunction closure (∧C, ∨C) and forgetting over sets (FO) cannot be done in polytime on tensor trains unless P = NP, by rank lower bounds.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| represent Boolean functions with TT_< instead of OBDD_< | Boolean function representations · Boolean functions under the same variable order | succinctness | Helped |
| use TT_< instead of OBDD_< | Boolean function operations · Queries and transformations supported in polytime by OBDD_< | polytime operation support | No clear effect |
| use TT_< for unbounded conjunction, unbounded disjunction, or forgetting a variable set | Tensor train Boolean function representations · Boolean function transformations | polytime operation support | Hurt |
Surprising findings
- Tensor trains are more succinct than OBDDs yet support exactly the same polytime operations, a trade-off that knowledge compilation maps usually rule out.
- The ∧C, ∨C and FO operations are intractable for tensor trains via rank lower bounds, despite being the same set as OBDD_< for the other operations.
Limitations
- Purely theoretical; no empirical evaluation of practical compilation or query runtime.
- Operations such as conjunction produce tensor trains whose rank is the product of input ranks, which may be large in practice.
- Succinctness relative to SDD and other NNF subsets is left open.
Experimental setup
Metrics: succinctness (polynomial size reduction) polytime operation support
Baselines: OBDD SDD DNNF
Builds on: OBDD knowledge compilation map tensor train decomposition sentential decision diagrams
Closest papers by meaning
- An And-Sum Circuit with Signed Edges That Is More Succinct than SDD (AAAI 2025 · similarity 0.88)
- A Compiler for Weak Decomposable Negation Normal Form (AAAI 2024 · similarity 0.86)
- New Compilation Languages Based on Restricted Weak Decomposability (AAAI 2025 · similarity 0.85)
- SHAP Meets Tensor Networks: Provably Tractable Explanations with Parallelism (NeurIPS 2025 · similarity 0.85)
- Over-parameterized Student Model via Tensor Decomposition Boosted Knowledge Distillation (NeurIPS 2024 · similarity 0.84)
- A Compositional Atlas for Algebraic Circuits (NeurIPS 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.