Characterization and lower bounds for branching program size using projective dimension

We study projective dimension, a graph parameter, denoted by pd(G) for a bipartite graph G, introduced by Pudlák and Rödl (1992). For a Boolean function f (on n bits), Pudlák and Rödl 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 ) implies lower bounds for bpsize(f ). Despite several attempts (Pudlák and Rödl (1992), Rónyai 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 Pudlák and Rödl (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 bitpdim(f ). We show the following results: (a) 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 c > 0 and for any function f , bitpdim(f )/6 ≤ bpsize(f ) ≤ (bitpdim(f )) c . (b) We introduce a new candidate family of functions f for showing super-polynomial lower bounds for bitpdim(f ). As our main result, for this family of functions, we demonstrate gaps between pd(f ) and the above two new measures for f : <eou>. We adapt Nechiporuk's techniques for our linear algebraic setting to prove the best-known bpsize lower bounds for bitpdim. Motivated by this linear algebraic setting of our main result, we derive exponential lower bounds for two restricted variants of pd(f ) and upd(f ) by observing that they are exactly equal to well-studied graph parameters-bipartite clique cover number and bipartite partition number, respectively.