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 ( 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 ( 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 0"> c 0 and for any function f , bpdim ( f ) 6 bpsize ( f ) ( 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 ( n ) , upd ( f ) = ( n ) , bpdim ( f ) = n 1 5 log n

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.