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 is polynomial in $n$
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).
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$.