# Boolean function with specific ОBDD representation

I am looking for a class of boolean functions on $n$ variables with the following property:

1. When represented by read twice palindromic ordered bdd (i.e. the order is 1..n n..1) the size of the OBDD is polynomial in $n$
2. Read once polynomial size OBDD doesn't exist for the boolean function.

I did some experiments with the CUDD package to no success.

Any ideas how to find an instance of such function?

(There is a chance such functions don't exist but I would not bet much money on this).

## 2 Answers

I think all pointer functions are hard for OBDDs and easy for a 2-OBDD. Example for such pointer functions are

• The hidden weighted bit function $HWB_n(x) = x_{sum}$ with $sum = x_1 + \ldots +x_n$ and $x_0 := 0$
• The indirect storage access (similar to the function in Noam's answer) $ISA_n$ with $n = 2^k$. Input is $(x,y)$ with $x \in \lbrace 0,1 \rbrace^n$ and $k \in \lbrace 0,1 \rbrace^k$. Let $\vert y \vert$ the integer represented by the binary number $y$. Then the input $y$ gives a part $x_{\vert y \vert},\ldots,x_{\vert y \vert +k-1}$ of the input $x$ (indices are taken mod $n$). Let $a$ be the integer represented by this part. The output of $ISA_n(x,y)$ is $x_a$.

It is known that for these function the OBDD size is exponential (see e.g. Branching Programs and Binary Decision Diagrams). But there is a polynomial 2-OBDD for these functions by parsing the address in the first phase and reading the relevant data in the second.

• This is indeed the right way to look at this. (My version was just designed so that the lower bound is especially easy to prove from scratch.)
– Noam
Feb 9 '11 at 4:34

Fix $k=\log n$ and define the following function on $n$ bits: take the first $k^2$ bits and view them as $k$ numbers in the range $1..2^k$: $p_1 ... p_k$. Now take the $p_1$'st bit, $p_2$'nd bit ... $p_k$'th bits of the input and view them as a $k$ bit number $p$. The output is the value of the $p$'th bit of the input.

A palindromic OBDD of size $exp(k^2)$ can solve it by first reading and remembering $p_1 ... p_k$, then reading these $k$ bits, on the first pass, and remembering $p$ and then reading the $p$'th bit on the 2nd pass.

Look at a single pass OBDD and let us restrict the function by dictating that $p_1 ... p_k$ will be equal to the last $k$ indices of the input, and thus $p$ is specified by the last $k$ bits of the input. It is easy to see that $\Omega(n)$ bits need to be remembered about the first $n-k^2-k$ non-restricted bits of the input in order for the value of the $p$'th bit to be recovered (this is the Index function in communication complexity -- see example 4.18 in Communication Complexity book, page 49).

This gives a gap $n^{\log n}$ vs. $exp(n)$ -- to get poly vs non-poly just use $N=n^{\log n}$ bits and ignore all but the first $n$.

• Thank you Noam. I am missing the logic, if the palindrome BDD is $exp(n)$ wouldn't it be bigger that the 1-OBDD? (taking logs)? Feb 9 '11 at 15:24
• exp(n) is on a 1-OBDD ("remember n bits" = size is exp(n)), and n^logn is on a 2-pass-OBDD ("remember k^2 bits" = size 2^{k^2}=n^logn)
– Noam
Feb 9 '11 at 19:01