We study projective dimension, a graph parameter (denoted by ${pd}(G)$ for a graph $G$), introduced by Pudlak and Rodl (1992). For a Boolean function $f$ (on $n$ bits), Pudlak and
Rodl associated a bipartite graph $G_f$ and showed that size of the optimal branching program computing $f$ (denoted by ${bpsize}(f)$) is at least ${pd}(G_f)$ (also denoted by
${pd}(f)$). Hence, proving lower bounds for ${pd}(f)$ imply lower bounds for ${bpsize}(f)$. Despite several attempts (Pudlak and Rodl (1992), Ronyai et.al, (2000)), proving
super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive.

We observe that there exist a Boolean function $f$ for which the gap between the ${pd}(f)$ and ${bpsize}(f)$) is $2^{\Omega(n)}$. Motivated by the argument in Pudlak and Rodl
(1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by ${upd}(f)$) and bitwise decomposable projective
dimension (denoted by ${bpdim}(f)$). We show the following results :

1 We observe that there exist a Boolean function $f$ for which the gap between ${upd}(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$, ${bpdim}(f)/6 \le {bpsize}(f)
\le ({bpdim}(f))^c$.

2. We introduce a new candidate function family $f$ for showing super-polynomial lower bounds for ${bpdim}(f)$. As our main result, we demonstrate gaps between ${pd}(f)$ and the above two
new measures for $f$ : ${pd}(f) = O(\sqrt{n})$, ${upd}(f) = \Omega(n)$, ${bpdim}(f) = \Omega\left(\frac{n^{1.5}}{\log n}\right)$

3. Although not related to branching program lower bounds, we derive exponential lower bounds for two restricted variants of ${pd}(f)$ and ${upd}(f)$ respectively by observing that they
are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.

Revised version. Updated to fix display errors in abstract.

We study projective dimension, a graph parameter (denoted by $\mathsf{pd}(G)$ for a graph $G$), introduced by Pudl\'ak and R\"odl (1992). For a Boolean function $f$(on $n$ bits), Pudl\'ak and R\"odl associated a bipartite graph $G_f$ and showed that size of the optimal branching program computing $f$ (denoted by $\mathsf{bpsize}(f)$) is at least $\mathsf{pd}(G_f)$ (also denoted by $\mathsf{pd}(f)$). Hence, proving lower bounds for $\mathsf{pd}(f)$ imply lower bounds for $\mathsf{bpsize}(f)$. Despite several attempts (Pudl\'ak and R\"odl (1992), R\'onyai et.al, (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive.

We observe that there exist a Boolean function $f$ for which the gap between the $\mathsf{pd}(f)$ and {\sf bpsize}$(f)$) is $2^{\Omega(n)}$. Motivated by the argument in (Pudlak, Rodl 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)$). We show the following results :

1. We observe that there exist a Boolean function $f$ for which the gap between $\mathsf{upd}(f)$ and {\sf 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$, $\mathsf{bpdim}(f)/6 \le \textrm{\sf bpsize}(f) \le (\mathsf{bpdim}(f))^c$

2. We introduce a new candidate function family $f$ for showing super-polynomial lower bounds for $\mathsf{bpdim}(f)$. As our main result, we demonstrate gaps between $\mathsf{pd}(f)$ and the above two new measures for $f$ :

$\textrm{$\mathsf{pd}(f) = O(\sqrt{n})$, $\mathsf{upd}(f) = \Omega(n)$, $\mathsf{bpdim}(f) = \Omega\left(\frac{n^{1.5}}{\log n}\right)$}$

3. Although not related to branching program lower bounds, we derive exponential lower bounds for two restricted variants of $\mathsf{pd}(f)$ and $\mathsf{upd}(f)$ respectively by observing that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively.

We study projective dimension, a graph parameter (denoted by $pd(G)$ for a graph $G$), introduced by (Pudlak, Rodl 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 (Pudlak, Rodl 1992 ; Babai, Ronyai, 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 (Pudlak, Rodl 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)$). We show the following results about these parameters:

1. 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})$.

2. We 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 large constant $c>0$ and for any function $f$, $bitpdim(G_f)/6 \le bpsize(f) \le (bitpdim(G_f))^c$.

3. 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. This immediately yields exponential lower bounds for these measures.