  OBDD-based graph algorithms deal with the characteristic function of the edge
set E of a graph $G = (V,E)$ which is represented by an OBDD and solve
optimization problems by mainly using functional operations. We present an
OBDD-based algorithm which uses randomization for the first time. In
particular, we give a maximal matching algorithm with $O(\log^3 \vert V \vert)$
functional operations in expectation. This algorithm may be of independent
interest. The experimental evaluation shows that this algorithm outperforms
known OBDD-based algorithms for the maximal matching problem.
  In order to use randomization, we investigate the OBDD complexity of $2^n$
(almost) $k$-wise independent binary random variables. We give a OBDD
construction of size $O(n)$ for $3$-wise independent random variables and show
a lower bound of $2^{\Omega(n)}$ on the OBDD size for $k \geq 4$. The best
known lower bound was $\Omega(2^n/n)$ for $k \approx \log n$ due to Kabanets.
We also give a very simple construction of $2^n$ $(\varepsilon, k)$-wise
independent binary random variables by constructing a random OBDD of width $O(n
k^2/\varepsilon)$.
