The Taub Faculty of Computer Science Events and Talks

Branching program is a combinatorial model of computation which models space in Turing machines. One of the holy grail in complexity theory is to understand the relationship between efficient space (class L, logarithmic space in input) and efficient time (class P, polynomial time in input). It is widely believed that there are problems which are in P but not in L. To prove that a problem is not in L it is enough to prove that it has no polynomial sized deterministic branching program computing it. But we do not yet know any lower bounds for deterministic branching programs which are better than quadratic (the best lower bound we know is due to Neciporuk and it is from 1966!).

In the 90's Pudlák and Rodl proposed a combinatorial/algebraic measure called projective dimension which lower bounds branching program size. Thus they showed that to prove branching program lower bounds it is enough to prove lower bounds on projective dimension. But the best know projective dimension lower bound is only linear (from the 90's!).

In this talk, we will see the connection between branching program size and projective dimension. We will then motivate the need for strengthening of projective dimension by showing a problem (non-explicit) for which the projective dimension is linear but branching program size is super-polynomial. To bridge this gap, we look at finer details of Pudlák and Rodl’s connection and introduce a derivative of of projective dimension which we call bitwise projective dimension. We will show that this measure captures branching program size up to polynomial factors. Thus for any problem which doesn’t have a polynomial size branching program computing it, the bitwise projective dimension will be super polynomial. And if time permits we will proceed to show a superlinear lower bound (which matches the best known lower bound for branching programs) on bitwise projective dimension using Neciporuk’s sub-function counting method.

This talk is a based on a recent work (http://eccc.hpi-web.de/report/2016/076/) with Krishnamoorthy Dinesh and Jayalal Sarma.