Branching Programs and Binary Decision Diagrams

Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01)

Recommendations

scientific article; zbMATH DE number 58305
scientific article; zbMATH DE number 846270
BDDs -- design, analysis, complexity, and applications.

Cited in

(only showing first 100 items - show all)

Partition search for non-binary constraint satisfaction
A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
Implicit computation of maximum bipartite matchings by sublinear functional operations
Exponential space complexity for OBDD-based reachability analysis
scientific article; zbMATH DE number 7447737 (Why is no real title available?)
Approximating Boolean functions by OBDDs
Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
Chain reduction for binary and zero-suppressed decision diagrams
Lower bounds for restricted read-once parity branching programs
Discrete optimization with decision diagrams
On the P versus NP intersected with co-NP question in communication complexity
Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
Randomized OBDDs for the most significant bit of multiplication need exponential space
Bounds on the OBDD-size of integer multiplication via universal hashing
The splitting power of branching programs of bounded repetition and CNFs of bounded width
Circuit complexity of regular languages
A moderately exponential time algorithm for \(k\)-IBDD satisfiability
Connecting knowledge compilation classes and width parameters
On limitations of structured (deterministic) DNNFs
Extension of the hierarchy for k-OBDDs of small width
Randomized OBDD-based graph algorithms
Improving OBDD attacks against stream ciphers
Randomized OBDD-based graph algorithms
Perspective on complexity measures targeting read-once branching programs
On threshold BDDs and the optimal variable ordering problem
Symbolic model checking for channel-based component connectors
Knowledge compilation meets database theory: compiling queries to decision diagrams
A rewriting approach to binary decision diagrams
A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
On the minimization of (complete) ordered binary decision diagrams
Yet harder knapsack problems
Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
Incremental branching programs
A Subatomic Proof System for Decision Trees
The characterization of branching dependencies
Computing Boolean functions via quantum hashing
The nonapproximability of OBDD minimization
On the use of binary decision diagrams for solving problems on simple games
De Bruijn sequences and complexity of symmetric functions
Dualization of Boolean functions using ternary decision diagrams
Randomized OBDDs for the most significant bit of multiplication need exponential size
Quantum versus classical online streaming algorithms with logarithmic size of memory
A polynomial-time construction of a hitting set for read-once branching programs of width 3
Quantum online algorithms with respect to space and advice complexity
Feature necessity \& relevancy in ML classifier explanations
Power indices of simple games and vector-weighted majority games by means of binary decision diagrams
Limitations of incremental dynamic programming
Generic constant-round oblivious sorting algorithm for MPC
Deterministic construction of QFAs based on the quantum fingerprinting technique
Width hierarchy for \(k\)-OBDD of small width
Priority functions for the approximation of the metric TSP
On multi-partition communication complexity
Symbolic topological sorting with OBDDs
Forms of representation for simple games: sizes, conversions and equivalences
On the relation between structured \(d\)-DNNFs and SDDs
Comparative complexity of quantum and classical OBDDs for total and partial functions
On the OBDD complexity of the most significant bit of integer multiplication
Two-way and one-way quantum and classical automata with advice for online minimization problems
BDDs -- design, analysis, complexity, and applications.
The simplified weighted sum function and its average sensitivity
Chordal networks of polynomial ideals
Incorporating bounds from decision diagrams into integer programming
On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
On the influence of the variable ordering for algorithmic learning using OBDDs
Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
Classical and Quantum Computations with Restricted Memory
Graph coloring lower bounds from decision diagrams
A nondeterministic space-time tradeoff for linear codes
On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
On the relative succinctness of sentential decision diagrams
scientific article; zbMATH DE number 7092118 (Why is no real title available?)
\texttt{VeriSIMPL 2}: an open-source software for the verification of max-plus-linear systems
Investigating dynamic causalities in reaction systems
Symbolic approximate time-optimal control
The optimal read-once branching program complexity for the direct storage access function
New results on the most significant bit of integer multiplication
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
On compiling structured CNFs to OBDDs
Extended BDD-Based Cryptanalysis of Keystream Generators
Lifting for simplicity: concise descriptions of convex sets
Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
On uncertainty versus size in branching programs.
Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
Exact OBDD bounds for some fundamental functions
On the contribution of backward jumps to instruction sequence expressiveness
Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
State-set branching: leveraging BDDs for heuristic search
Theoretical insights and algorithmic tools for decision diagram-based optimization
An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
Exact OBDD Bounds for Some Fundamental Functions
A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
On Tseitin formulas, read-once branching programs and treewidth
Branching constraint satisfaction problems and Markov decision problems compared
Graph coloring with decision diagrams
Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance
A note on the decoding complexity of error-correcting codes
Lower bounds on the OBDD size of two fundamental functions' graphs
On approximation by \(^{\oplus}\)-OBDDs
Larger lower bounds on the OBDD complexity of integer multiplication

This page was built for publication: Branching Programs and Binary Decision Diagrams

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4485697)