| Title | : | Branching Program Size Lower Bounds via Projective Dimension |
| Speaker | : | Sajin Koroth (IITM) |
| Details | : | Fri, 16 Dec, 2016 11:00 AM @ BSB 361 |
| Abstract: | : | Abstract : Branching program is a 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 Pudlak 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 why branching programs are an important combinatorial model of computation. Then we will motivate the study of projective dimension by showing its connection to branching program size by revisiting the original proof of Pudlak and Rodl. As Projective dimension is an algebraic measure which it brings more tools to the lower bounds. Yet the best known lower bound for projective dimension is weaker than the best known branching program lower bound. We explain this a gap between branching program size and 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 Pudlak and Rodls 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 it is guaranteed that for any problem which does not have a polynomial size branching program computing it (outside L), the bitwise projective dimension will be super-polynomially large. Though bitwise projective dimension captures branching program size up to a polynomial factor, the best known branching program lower bound still does not give any super polynomial lower bound for bitwise projective dimension. To address this, we will then revisit the super-linear lower of Nechiprouk and show a super-linear lower bound (which matches the best known lower bound for branching programs) on bitwise projective dimension. |
