Lower bounds for depth-restricted branching programs

We 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 POLY n, d ∗ (n ∈ N prime, d ≤ n) whether a given mapping g: F n → F n is a polynomial over F n 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 POLY n, δn ∗ (δ ∈ (0, 1 2 )).

Authors

• Matthias Krause

Keywords

No keywords are indexed for this paper.