Dinesh, Krishnamoorthy ;
Koroth, Sajin ;
Sarma, Jayalal
Characterization and Lower Bounds for Branching Program Size Using Projective Dimension
Abstract
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 superlinear 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:
(a) 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 large constant c>0 and for any function f, bpdim(f)/6 <= bpsize(f) <= (bpdim(f))^c.
(b) We introduce a new candidate function family f for showing superpolynomial 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({n^{1.5}}/{log(n)}).
(c) 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 wellstudied graph parameters  bipartite clique cover number and bipartite partition number respectively.
BibTeX  Entry
@InProceedings{dinesh_et_al:LIPIcs:2016:6872,
author = {Krishnamoorthy Dinesh and Sajin Koroth and Jayalal Sarma},
title = {{Characterization and Lower Bounds for Branching Program Size Using Projective Dimension}},
booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
pages = {37:137:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770279},
ISSN = {18688969},
year = {2016},
volume = {65},
editor = {Akash Lal and S. Akshay and Saket Saurabh and Sandeep Sen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6872},
URN = {urn:nbn:de:0030drops68722},
doi = {10.4230/LIPIcs.FSTTCS.2016.37},
annote = {Keywords: Projective Dimension, Lower Bounds, Branching Program Size}
}
10.12.2016
Keywords: 

Projective Dimension, Lower Bounds, Branching Program Size 
Seminar: 

36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)

Issue date: 

2016 
Date of publication: 

10.12.2016 