Branching Programs and Binary Decision Diagrams

DOI10.1137/1.9780898719789zbMATH Open0956.68068OpenAlexW143396352MaRDI QIDQ4485697FDOQ4485697

Authors: Ingo Wegener 

Publication date: 18 June 2000

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

Recommendations

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

zbMATH Keywords

data structurescomplexity theoryBoolean functionefficient algorithmsbranching programdecision diagram

Mathematics Subject Classification ID

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

Cited In (only showing first 100 items - show all)

• Graph coloring lower bounds from decision diagrams
• Incorporating bounds from decision diagrams into integer programming
• On the relative succinctness of sentential decision diagrams
• On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth
• On compiling structured CNFs to OBDDs
• The optimal read-once branching program complexity for the direct storage access function
• 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.
• Exact OBDD Bounds for Some Fundamental Functions
• Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
• On Tseitin formulas, read-once branching programs and treewidth
• Branching constraint satisfaction problems and Markov decision problems compared
• 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
• Size-treewidth tradeoffs for circuits computing the element distinctness function
• A direct construction of polynomial-size OBDD proof of pigeon hole problem
• Target cuts from relaxed decision diagrams
• Compact representation of near-optimal integer programming solutions
• ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES
• Outer approximation for integer nonlinear programs via decision diagrams
• Optimal ordered binary decision diagrams for read-once formulas
• A moderately exponential time algorithm for \(k\)-IBDD satisfiability
• Second-order finite automata
• Variable ordering for decision diagrams: a portfolio approach
• Title not available (Why is that?)
• A lower bound for integer multiplication on randomized ordered read-once branching programs.
• A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy
• 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
• A hierarchy result for read-once branching programs with restricted parity nondeterminism
• On compiling structured CNFs to OBDDs
• Proof complexity of symbolic QBF reasoning
• Title not available (Why is that?)
• Circuit complexity of regular languages
• A moderately exponential time algorithm for \(k\)-IBDD satisfiability
• Randomized OBDDs for the most significant bit of multiplication need exponential space
• Connecting knowledge compilation classes and width parameters
• On limitations of structured (deterministic) DNNFs
• Randomized OBDD-based graph algorithms
• Randomized OBDD-based graph algorithms
• A rewriting approach to binary decision diagrams
• Restricted nondeterministic read-once branching programs and an exponential lower bound for integer multiplication
• Incremental branching programs
• The characterization of branching dependencies
• On the relation between structured \(d\)-DNNFs and SDDs
• Two-way and one-way quantum and classical automata with advice for online minimization problems
• On the OBDD Complexity of Threshold Functions and the Variable Ordering Problem
• Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs
• On the influence of the variable ordering for algorithmic learning using OBDDs
• Title not available (Why is that?)
• Lifting for simplicity: concise descriptions of convex sets
• Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
• Graph coloring with decision diagrams
• A simpler rate-optimal CPIR protocol
• Larger Lower Bounds on the OBDD Complexity of Integer Multiplication
• Real numbers and BDDs
• State space analysis of Petri nets with relation-algebraic methods
• Exact Multiple Sequence Alignment by Synchronized Decision Diagrams
• Error-Free Affine, Unitary, and Probabilistic OBDDs
• Nondeterministic unitary OBDDs
• An algorithm for reducing binary branchings
• Minimization problems for parity OBDDs
• A faster implementation of EQ and SE queries for switch-list representations
• Tractable representations for Boolean functional synthesis
• Chain reduction for binary and zero-suppressed decision diagrams
• Lower bounds for restricted read-once parity branching programs
• The splitting power of branching programs of bounded repetition and CNFs of bounded width
• Perspective on complexity measures targeting read-once branching programs
• Improving OBDD attacks against stream ciphers
• A Subatomic Proof System for Decision Trees
• 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
• Randomized OBDDs for the most significant bit of multiplication need exponential size
• Feature necessity \& relevancy in ML classifier explanations
• Deterministic construction of QFAs based on the quantum fingerprinting technique
• Generic constant-round oblivious sorting algorithm for MPC
• The simplified weighted sum function and its average sensitivity
• Chordal networks of polynomial ideals
• On the OBDD complexity of the most significant bit of integer multiplication
• On the OBDD Complexity of the Most Significant Bit of Integer Multiplication
• A nondeterministic space-time tradeoff for linear codes
• New results on the most significant bit of integer multiplication
• Extended BDD-Based Cryptanalysis of Keystream Generators
• \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
• An exponential lower bound for a constraint propagation proof system based on ordered binary decision diagrams
• Exact OBDD bounds for some fundamental functions
• State-set branching: leveraging BDDs for heuristic search
• Theoretical insights and algorithmic tools for decision diagram-based optimization
• On the contribution of backward jumps to instruction sequence expressiveness
• A simpler counterexample to a long-standing conjecture on the complexity of Bryant's apply algorithm
• Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs
• Larger lower bounds on the OBDD complexity of integer multiplication
• Approximation of boolean functions by combinatorial rectangles
• New size hierarchies for two way automata
• Relation-algebraic modeling and solution of chessboard independence and domination problems

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)