Branching Programs and Binary Decision Diagrams

DOI10.1137/1.9780898719789zbMath0956.68068OpenAlexW143396352MaRDI QIDQ4485697

Publication date: 18 June 2000

Full work available at URL: https://doi.org/10.1137/1.9780898719789

data structures Boolean function decision diagram complexity theory efficient algorithms branching program

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

Related Items (only showing first 100 items - show all)

Graph Coloring Lower Bounds from Decision Diagrams ⋮ A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3 ⋮ Lifting for Simplicity: Concise Descriptions of Convex Sets ⋮ Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations ⋮ A Moderately Exponential Time Algorithm for k-IBDD Satisfiability ⋮ Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs ⋮ A Subatomic Proof System for Decision Trees ⋮ On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width ⋮ Branching Programs for Tree Evaluation ⋮ Randomized OBDD-Based Graph Algorithms ⋮ On Compiling Structured CNFs to OBDDs ⋮ Unnamed Item ⋮ Computing Boolean Functions via Quantum Hashing ⋮ Chordal Networks of Polynomial Ideals ⋮ Quantum versus classical online streaming algorithms with logarithmic size of memory ⋮ Deterministic construction of QFAs based on the quantum fingerprinting technique ⋮ On the OBDD Complexity of the Most Significant Bit of Integer Multiplication ⋮ Attacking Bivium Using SAT Solvers ⋮ Decision Diagrams for Discrete Optimization: A Survey of Recent Advances ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Optimization Bounds from Binary Decision Diagrams ⋮ Unnamed Item ⋮ Target Cuts from Relaxed Decision Diagrams ⋮ An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams ⋮ ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES ⋮ Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs ⋮ Real Numbers and BDDs ⋮ Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems ⋮ Circuit complexity of regular languages ⋮ Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication ⋮ On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem ⋮ Exact OBDD Bounds for Some Fundamental Functions ⋮ Extended BDD-Based Cryptanalysis of Keystream Generators ⋮ The simplified weighted sum function and its average sensitivity ⋮ Larger Lower Bounds on the OBDD Complexity of Integer Multiplication ⋮ Discrete Optimization with Decision Diagrams ⋮ Randomized OBDDs for the Most Significant Bit of Multiplication Need Exponential Size ⋮ Chain reduction for binary and zero-suppressed decision diagrams ⋮ Improving OBDD attacks against stream ciphers ⋮ Generic Constant-Round Oblivious Sorting Algorithm for MPC ⋮ Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs ⋮ Exact Multiple Sequence Alignment by Synchronized Decision Diagrams ⋮ Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs. ⋮ A Simpler Rate-Optimal CPIR Protocol ⋮ 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 ⋮ A Polynomial-Time Construction of a Hitting Set for Read-Once Branching Programs of Width 3 ⋮ Investigating dynamic causalities in reaction systems ⋮ Very narrow quantum OBDDs and width hierarchies for classical OBDDs ⋮ On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs ⋮ Incorporating bounds from decision diagrams into integer programming ⋮ Sequential testing of complex systems: a review ⋮ Randomized OBDD-based graph algorithms ⋮ On multi-partition communication complexity ⋮ Partition search for non-binary constraint satisfaction ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice ⋮ On the read-once property of branching programs and CNFs of bounded treewidth ⋮ Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance ⋮ A note on the decoding complexity of error-correcting codes ⋮ Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations ⋮ Lower bounds on the OBDD size of two fundamental functions' graphs ⋮ On approximation by \(^{\oplus}\)-OBDDs ⋮ A rewriting approach to binary decision diagrams ⋮ On the OBDD representation of some graph classes ⋮ Variable ordering for decision diagrams: a portfolio approach ⋮ Symbolic model checking for channel-based component connectors ⋮ State-set branching: leveraging BDDs for heuristic search ⋮ Second-order finite automata ⋮ Data structures for symbolic multi-valued model-checking ⋮ Extension of the hierarchy for \(k\)-OBDDs of small width ⋮ Theoretical insights and algorithmic tools for decision diagram-based optimization ⋮ Approximating Boolean functions by OBDDs ⋮ Nondeterministic unitary OBDDs ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ Knowledge compilation meets database theory: compiling queries to decision diagrams ⋮ Partially-shared zero-suppressed multi-terminal BDDs: Concept, algorithms and applications ⋮ On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth ⋮ Exponential space complexity for OBDD-based reachability analysis ⋮ On compiling structured CNFs to OBDDs ⋮ On the use of binary decision diagrams for solving problems on simple games ⋮ Relation-algebraic modeling and solution of chessboard independence and domination problems ⋮ Compact representation of near-optimal integer programming solutions ⋮ 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. ⋮ Forms of representation for simple games: sizes, conversions and equivalences ⋮ Randomized OBDDs for the most significant bit of multiplication need exponential space ⋮ 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 ⋮ Comparative complexity of quantum and classical OBDDs for total and partial functions ⋮ Size-treewidth tradeoffs for circuits computing the element distinctness function ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ Symbolic bounded synthesis ⋮ Exact OBDD bounds for some fundamental functions ⋮ Priority functions for the approximation of the metric TSP

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