Characterization and Lower Bounds for Branching Program Size using Projective Dimension

We study projective dimension, a graph parameter (denoted by pd$(G)$ for a graph $G$), introduced by (Pudl'ak, R"odl 1992), who showed that proving lower bounds for pd$(G_f)$ for bipartite graphs $G_f$ associated with a Boolean function $f$ imply size lower bounds for branching programs computing $f$. Despite several attempts (Pudl'ak, R"odl 1992 ; Babai, R'{o}nyai, Ganapathy 2000), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We show that there exist a Boolean function $f$ (on $n$ bits) for which the gap between the projective dimension and size of the optimal branching program computing $f$ (denoted by bpsize$(f)$), is $2^{\mathrm{\Omega }(n)}$. Motivated by the argument in (Pudl'ak, R"odl 1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by upd$(G)$) and bitwise decomposable projective dimension (denoted by bitpdim$(G)$). As our main result, we show that there is an explicit family of graphs on $N = 2^n$verticessuchthattheprojectivedimensionis$O(\sqrt{n})$, the projective dimension with intersection dimension $1$ is $\mathrm{\Omega }(n)$ and the bitwise decomposable projective dimension is $\mathrm{\Omega }(\frac{n^{1.5}}{\log n})$. We also show that there exist a Boolean function $f$ (on $n$ bits) for which the gap between upd$(G_f)$ and bpsize$(f)$ is $2^{\mathrm{\Omega }(n)}$. In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a constant $c>0$ and for any function $f$, $$\text{bitpdim}$(G_f)/6 \le $\text{bpsize}$(f) \le ($\text{bitpdim}$(G_f))^c$. We also study two other variants of projective dimension and show that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.