Lower bounds for depth-restricted branching programs

AbstractWe present a new method for proving lower bounds on the complexity of branching programs and consider k-times-only branching programs. While exponential and nearly exponential lower bounds on the complexity of one-time-only branching programs were proved for many problems, there are still missing methods of proving lower bounds for k-times-only programs (k > 1). We prove exponential lower bounds for k-times-only branching programs which have the additional restriction that the input bits are read k times, yet blockwise and in each block in the same order. This is done both for the algebraic decision problem POLYn,d∗ (n ∈ N prime, d ≤ n) whether a given mapping g: Fn → Fn is a polynomial over Fn of degree at most d, and for the corresponding monotone problem over quadratic Boolean matrices. As a consequence we obtain a sharp bound of order Θ(n · log(n)) on the communication complexity of POLYn, δn∗ (δ ∈ (0, 12))