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)

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
Proof complexity of positive branching programs
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
Pebbles and branching programs for tree evaluation
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
On the complexity of computing the shuffled inequality function in classical and quantum NOBDDs
A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
Quantum algorithm for finding the optimal variable ordering for binary decision diagrams
On Tseitin formulas, read-once branching programs and treewidth
A review of decision diagrams in system reliability modeling and analysis
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
Approximation of boolean functions by combinatorial rectangles
Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
A simpler rate-optimal CPIR protocol
New size hierarchies for two way automata
Size-treewidth tradeoffs for circuits computing the element distinctness function
Larger Lower Bounds on the OBDD Complexity of Integer Multiplication
Relation-algebraic modeling and solution of chessboard independence and domination problems
An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order
A direct construction of polynomial-size OBDD proof of pigeon hole problem
Real numbers and BDDs
State space analysis of Petri nets with relation-algebraic methods
Attacking Bivium Using SAT Solvers
Optimization Bounds from Binary Decision Diagrams
Compact representation of near-optimal integer programming solutions
Data structures for symbolic multi-valued model-checking
Target cuts from relaxed decision diagrams
Outer approximation for integer nonlinear programs via decision diagrams
ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
Optimal ordered binary decision diagrams for read-once formulas
A moderately exponential time algorithm for k-IBDD satisfiability
Exact Multiple Sequence Alignment by Synchronized Decision Diagrams
On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
Very narrow quantum OBDDs and width hierarchies for classical OBDDs
Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
Branching Programs for Tree Evaluation
Sequential testing of complex systems: a review
On the read-once property of branching programs and CNFs of bounded treewidth
Second-order finite automata
On the computational power of probabilistic and quantum branching program
Catalytic branching programs from groups and general protocols
Partially-shared zero-suppressed multi-terminal BDDs: Concept, algorithms and applications
Variable ordering for decision diagrams: a portfolio approach
Symbolic bounded synthesis
scientific article; zbMATH DE number 58305 (Why is no real title available?)
Error-Free Affine, Unitary, and Probabilistic OBDDs
A lower bound for integer multiplication on randomized ordered read-once branching programs.
Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
On the OBDD representation of some graph classes
On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
Quantum branching programs and space-bounded nonuniform quantum complexity
A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
On symbolic OBDD-based algorithms for the minimum spanning tree problem
Nondeterministic unitary OBDDs
Implicit computation of maximum bipartite matchings by sublinear functional operations
On efficient implicit OBDD-based algorithms for maximal matchings
Feature necessity and relevancy in machine learning explanations
An algorithm for reducing binary branchings
On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
Minimization of decision trees is hard to approximate
The computational power of Benenson automata
A hierarchy result for read-once branching programs with restricted parity nondeterminism
Minimization problems for parity OBDDs
On compiling structured CNFs to OBDDs

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)