OBDDs and (Almost) $k$-wise Independent Random Variables

Abstract

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|V|)$ 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\ge 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$ $(\epsilon ,k)$-wise independent binary random variables by constructing a random OBDD of width $O(n{k}^2/\epsilon )$.