Characterization and Lower Bounds for Branching Program Size using Projective Dimension

Krishnamoorthy Dinesh, Sajin Koroth, Jayalal Sarma

We study projective dimension, a graph parameter (denoted by pd$(G)$ for a graph $G$), introduced by (Pudlák, Rödl 1992), who showed that proving lower bounds for pd$(G_f)$ for bip…