Branching Programs and Binary Decision Diagrams
Branching programs, BPs, (or, synonymously, binary decision diagrams, BDDs) are an important way, that became very popular in the previous decade, to represent Boolean functions. Their attractiveness stems from two facts: From a theoretical point of view, the study of branching programs contributes to the broader study of the complexity of Boolean functions, a field of immense importance in theoretical computer science and discrete mathematics. Second, branching programs are relevant for applied computer science since a number of important operations on Boolean functions can be performed efficiently when these are given as branching programs. These operations include for instance evaluation, synthesis, satisfiability test, equivalence test, or minimization. Thus, branching programs serve as a good data structure for Boolean functions. Both these motivations for the study of BPs are followed in the book. After a one chapter introduction to the field, the first part of the book, consisting of eleven chapters, presents theoretical results. Different chapters treat different types of branching programs, such as (most prominently) OBDDs (ordered BDDs), read-once BDDs, randomized BDDs, and some more. The presented topics include efficient algorithms to manipulate BPs, upper bounds for the BDD-size of important problems (e.g., addition, multiplication, division, storage access) as well as lower bounds. The first part ends with a summary of theoretical results, containing a table of the time complexity of algorithms for operations on BDDs, a list of upper and lower bounds of a number of functions w.r.t.~size for different types of BDDs, and two inclusion diagrams among complexity classes defined by OBDDs and free BDDs. The second part of the book, consisting of three chapters, turns to applications of BDDs, including circuit verification, model checking, logic minimization and synthesis, etc. Though certainly the book primarily serves as a monograph for researchers, the author also outlines how a theoretically inclined and how a practically oriented course might be taught based on the contents of the book. Also for this purpose, every chapter ends with a number of exercises, graded ``E (easy), ``M (middle), or ``D (difficult). Also helpful will be the URL of a page on the web containing solutions of exercises and a continuously updated list of errors and typos. There are only very few books devoted to the topic of branching programs, and this alone would make the book a welcome contribution. But far more than that: The book has a remarkably broad scope and while presenting all the wonderful complexity results for branching programs that appeared in the past few years (the vast majority of papers in the bibliography were published very recently in the second half of the nineties of the previous century), the author does not disregard applications. The book will be very welcome by computer scientists and mathematicians who look for a comprehensive presentation of the theory of branching programs and want to get a quick overview of the possible applications.
- Representation of graphs by OBDDs
- A very simple function that requires exponential size nondeterministic graph-driven read-once branching programs
- On the OBDD size for graphs of bounded tree- and clique-width
- On threshold BDDs and the optimal variable ordering problem
- On the P versus NP intersected with co-NP question in communication complexity
- The characterization of branching dependencies
- A rewriting approach to binary decision diagrams
- Approximation of boolean functions by combinatorial rectangles
- On uncertainty versus size in branching programs.
- Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
- A lower bound for integer multiplication on randomized ordered read-once branching programs.
- BDDs -- design, analysis, complexity, and applications.
- Optimal ordered binary decision diagrams for read-once formulas
- Randomized OBDD-based graph algorithms
- Exponential space complexity for OBDD-based reachability analysis
- Size-treewidth tradeoffs for circuits computing the element distinctness function
- Quantum branching programs and space-bounded nonuniform quantum complexity
- The nonapproximability of OBDD minimization
- On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs
- Branching constraint satisfaction problems and Markov decision problems compared
- Sequential testing of complex systems: a review
- On multi-partition communication complexity
- On the use of binary decision diagrams for solving problems on simple games
- Relation-algebraic modeling and solution of chessboard independence and domination problems
- Randomized OBDDs for the most significant bit of multiplication need exponential space
- Exact OBDD bounds for some fundamental functions
- New size hierarchies for two way automata
- A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
- Outer approximation for integer nonlinear programs via decision diagrams
- On the relation between structured \(d\)-DNNFs and SDDs
- On Tseitin formulas, read-once branching programs and treewidth
- Graph coloring with decision diagrams
- Proof complexity of symbolic QBF reasoning
- Two-way and one-way quantum and classical automata with advice for online minimization problems
- Variable ordering for decision diagrams: a portfolio approach
- Second-order finite automata
- Compact representation of near-optimal integer programming solutions
- Minimization problems for parity OBDDs
- On the relative succinctness of sentential decision diagrams
- Very narrow quantum OBDDs and width hierarchies for classical OBDDs
- On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-k-times branching programs
- Partition search for non-binary constraint satisfaction
- Symbolic model checking for channel-based component connectors
- State-set branching: leveraging BDDs for heuristic search
- Theoretical insights and algorithmic tools for decision diagram-based optimization
- Nondeterministic unitary OBDDs
- Reordering method and hierarchies for quantum and classical ordered binary decision diagrams
- On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
- On compiling structured CNFs to OBDDs
- New results on the most significant bit of integer multiplication
- A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
- On the OBDD complexity of the most significant bit of integer multiplication
- Priority functions for the approximation of the metric TSP
- A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
- Symbolic topological sorting with OBDDs
- Minimization of decision trees is hard to approximate
- Lower bounds for restricted read-once parity branching programs
- Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication
- State space analysis of Petri nets with relation-algebraic methods
- A hierarchy result for read-once branching programs with restricted parity nondeterminism
- On the influence of the variable ordering for algorithmic learning using OBDDs
- The computational power of Benenson automata
- Bounds on the OBDD-size of integer multiplication via universal hashing
- On converting CNF to DNF
- On the computational power of probabilistic and quantum branching program
- \texttt{VeriSIMPL 2}: an open-source software for the verification of max-plus-linear systems
- Investigating dynamic causalities in reaction systems
- Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
- Discrete optimization with decision diagrams
- 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
- Computing Boolean functions via quantum hashing
- An algorithm for reducing binary branchings
- Optimization Bounds from Binary Decision Diagrams
- Almost k-wise independent sets establish hitting sets for width-3 1-branching programs
- Randomized OBDDs for the most significant bit of multiplication need exponential size
- Generic constant-round oblivious sorting algorithm for MPC
- On the read-once property of branching programs and CNFs of bounded treewidth
- Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
- On the OBDD representation of some graph classes
- Branching Programs for Tree Evaluation
- On compiling structured CNFs to OBDDs
- Improving OBDD attacks against stream ciphers
- A comparison of BDD-based parity game solvers
- A moderately exponential time algorithm for \(k\)-IBDD satisfiability
- Randomized OBDD-based graph algorithms
- On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
- Attacking Bivium Using SAT Solvers
- Extension of the hierarchy for k-OBDDs of small width
- Knowledge compilation meets database theory: compiling queries to decision diagrams
- On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
- Larger Lower Bounds on the OBDD Complexity of Integer Multiplication
- scientific article; zbMATH DE number 58305 (Why is no real title available?)
- scientific article; zbMATH DE number 512863 (Why is no real title available?)
- On symbolic OBDD-based algorithms for the minimum spanning tree problem
- Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs
- Symbolic bounded synthesis
- On efficient implicit OBDD-based algorithms for maximal matchings
- Implicit computation of maximum bipartite matchings by sublinear functional operations
- Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
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)
