Title: Incremental branching programs
Speaker: Pierre McKenzie, Université de Montréal
Date: October 18, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, CoRE 301 Room A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Motivated by the Logspace versus P question in complexity theory, we introduce incremental branching programs. These capture the best strategy known to space-efficiently solve the P-complete problem GEN (given an arbitrary binary operation on {1, 2, ..., n}, does 1 generate n by iterated product?). We show that our model captures and possibly supersedes previously studied structured models of computation for GEN, namely marking machines [Cook 74] and Poon's extension [Poon 93] of jumping automata on graphs [Cook-Rackoff 80]. From these relationships, or from known monotone circuit depth lower bounds, we derive exponential lower bounds for variants of our model although we are unable to prove any strong lower bounds for the most general variant of incremental branching programs.
Joint work with Anna Gal and Michal Koucky.