On the Complexity of the Hidden Weighted Bit Function for Various BDD Models

DOI10.1051/ita:1999108zbMath0946.68042OpenAlexW2013638043MaRDI QIDQ4265532

Ingo Wegener, Beate Bollig, Martin Sauerhoff, Martin Loebbing

Publication date: 22 September 1999

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=ITA_1999__33_2_103_0/

zbMATH Keywords

ordered binary decision diagrams

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Lower bounds on the OBDD size of two fundamental functions' graphs ⋮ On the second-order nonlinearity of the hidden weighted bit function ⋮ Approximating Boolean functions by OBDDs ⋮ On CDCL-Based Proof Systems with the Ordered Decision Strategy ⋮ On symbolic OBDD-based algorithms for the minimum spanning tree problem ⋮ Priority functions for the approximation of the metric TSP ⋮ On efficient implicit OBDD-based algorithms for maximal matchings ⋮ On the relative succinctness of sentential decision diagrams ⋮ On limitations of structured (deterministic) DNNFs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph driven BDDs -- a new data structure for Boolean functions
• Probabilistic verification of Boolean functions
• Lower bounds to the complexity of symmetric Boolean functions
• Some notes on threshold circuits, and multiplication in depth 4
• On the relation between BDDs and FDDs
• Short monotone formulae for the majority function
• On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
• Graph-Based Algorithms for Boolean Function Manipulation
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• Communication Complexity