About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theory of Computing
Paper
A non-linear time lower bound for boolean branching programs
Abstract
We give an exponential lower bound for the size of any linear-time Boolean branching program computing an explicitly given function. More precisely, we prove that for all positive integers k and for all sufficiently small ε > 0, if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2εn which, for all inputs X ⊆{0,1,…,n−1}, computes in time kn the parity of the number of elements of theset of all pairs 〈x, y〉 with the property x ∈ X, y ∈ X, x < y, x + y ∈ X. For the proof of this fact we show that if A = (ai,j)mi=0,j=0 is a random n by n matrix over the field with 2 elements with the condition that “A is constant on each minor diagonal,” then with high probability the rank of each δ n by δ n submatrix of A is at least cδ | log δ |−2n, where c > 0 is an absolute constant and n is sufficiently large with respect to δ. (A preliminary version of this paper has appeared in the Proceedings of the 40th IEEE Symposium on Foundations of Computer Science.).