Branching Programs and Binary Decision Diagrams
From MaRDI portal
Publication:4485697
DOI10.1137/1.9780898719789zbMATH Open0956.68068OpenAlexW143396352MaRDI QIDQ4485697FDOQ4485697
Publication date: 18 June 2000
Full work available at URL: https://doi.org/10.1137/1.9780898719789
Recommendations
data structurescomplexity theoryBoolean functionefficient algorithmsbranching programdecision diagram
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)
- 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
- 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 tseitin formulas, read-once branching programs and treewidth
- On uncertainty versus size in branching programs.
- Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines.
- Randomized OBDD-Based Graph Algorithms
- Exact OBDD Bounds for Some Fundamental Functions
- Polynomial-size binary decision diagrams for the exactly half-\(d\)-hyperclique problem reading each input bit twice
- 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
- On Compiling Structured CNFs to OBDDs
- A direct construction of polynomial-size OBDD proof of pigeon hole problem
- A Moderately Exponential Time Algorithm for k-IBDD Satisfiability
- 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
- Graph Coloring Lower Bounds from Decision Diagrams
- Satisfiable Tseitin Formulas Are Hard for Nondeterministic Read-Once Branching Programs.
- Title not available (Why is that?)
- Circuit complexity of regular languages
- 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
- 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
- Target Cuts from Relaxed Decision Diagrams
- 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
- 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
- Computing Boolean Functions via Quantum Hashing
- 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
- Implicit Computation of Maximum Bipartite Matchings by Sublinear Functional Operations
- 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
- Attacking Bivium Using SAT Solvers
- An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order
- Optimization Bounds from Binary Decision Diagrams
- Data structures for symbolic multi-valued model-checking
- 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 computational power of probabilistic and quantum branching program
- On the read-once property of branching programs and CNFs of bounded treewidth
- Partially-shared zero-suppressed multi-terminal BDDs: Concept, algorithms and applications
- Symbolic bounded synthesis
- On the Expressive Power of CNF Formulas of Bounded Tree- and Clique-Width
- Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations
- On the OBDD representation of some graph classes
- Quantum branching programs and space-bounded nonuniform quantum complexity
- On symbolic OBDD-based algorithms for the minimum spanning tree problem
- Implicit computation of maximum bipartite matchings by sublinear functional operations
- On efficient implicit OBDD-based algorithms for maximal matchings
- Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
- Minimization of decision trees is hard to approximate
- Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
- The computational power of Benenson automata
- Representation of graphs by OBDDs
- On the OBDD size for graphs of bounded tree- and clique-width
- On converting CNF to DNF
- Decision Diagrams for Discrete Optimization: A Survey of Recent Advances
- A Sufficient Condition for Sets Hitting the Class of Read-Once Branching Programs of Width 3
- Partition search for non-binary constraint satisfaction
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)
