  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^{\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$ vertices such that the projective dimension is $O(\sqrt{n})$, the
projective dimension with intersection dimension $1$ is $\Omega(n)$ and the
bitwise decomposable projective dimension is $\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^{\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$, $\textrm{bitpdim}(G_f)/6 \le
\textrm{bpsize}(f) \le (\textrm{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.
