The binary-decision-diagrams tag has no wiki summary.
9
votes
0answers
115 views
Algorithms on graphs represented using BDDs
The simplest representations for graphs use adjacency matrices/lists, meaning that each node and edge is explicitly represented. The importance of implicit representations for graphs exhibiting strong ...
4
votes
1answer
140 views
Trade off between width and depth of free BDDs for total functions
Terminology
A binary decision diagram is a directed acyclic graph with one source (root), and two sinks ($A$ and $B$). Each non-sink nodes is labeled by an integer $i \in \{1,...,n\}$ and has ...
3
votes
1answer
213 views
Bounds on the size of smallest decision tree for a boolean function?
Consider a boolean function $f : V \rightarrow \{0,1\}$ with $m$ true points. Are there any non-trivial bounds in $m$ on the size of the smallest decision tree for $f$?
It seems to me that assuming ...
6
votes
0answers
118 views
Does the cohomological approach to Boolean complexity nicely model any BDD heuristics?
In this question, I learned that complexity theorists had considered using Grothendieck topologies to model Boolean circuits. This has not, apparently, led to any new lower bounds yet, but I'm not so ...
9
votes
0answers
172 views
Lower bound method for ordered binary decision diagrams
This is an idea/question inspired by the question and answer of Boolean functions with exponential size OBDD representation in all orders except one order?:
If you want to prove some exponential ...
5
votes
2answers
211 views
Boolean functions with exponential size OBDD representation in all orders except one order?
Are there boolean functions with exponential size OBDD representation in all orders except one order?
...exponential size in all orders except very few orders?
The exceptional orders should be ...
7
votes
2answers
205 views
Boolean function with specific ОBDD representation
I am looking for a class of boolean functions on $n$ variables with the following property:
When represented by read twice palindromic ordered bdd (i.e. the order is 1..n n..1) the size of the OBDD ...
14
votes
1answer
349 views
Most significant bit of integer multiplication and binary decision diagrams
Let $x$ and $y$ two binary numbers with $n$ bits and $z = x \cdot y\ $ the binary number (length $2n$) of the product of $x$ and $y$. We want to compute the most siginifcant bit $z_{2n-1}$ of the ...
7
votes
4answers
206 views
Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?
Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for representing boolean functions of multiple variables $f(x_1,x_2,...,x_n)$. I would like to get an intuition for how ...
