Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
83 views

Compatible partial permutations

Please, correct my terminology as I am not a combinatorician (I am using http://en.wikipedia.org/wiki/Partial_permutation). Please, refer me to the solution if this is a solved problem. Let $P_k$ ...
9
votes
0answers
149 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
158 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
268 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
125 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
190 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 ...
6
votes
2answers
237 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
216 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
461 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 ...
8
votes
4answers
225 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 ...