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
FOCS 1999
Conference paper
Non-linear time lower bound for Boolean branching programs
Abstract
We prove that for all positive integer k and for all sufficiently small qq > 0 if n is sufficiently large then there is no Boolean (or 2-way) branching program of size less than 2 qqn which for all inputs X qq {0, 1, ..., n - 1} computes in time kn the parity of the number of elements of the set of all pairs 〈x,y〉 with the property x qq X, y qq X, x < y, x + y qq X. For the proof of this fact we show that if A = (a i,j) i=0,j=0n is a random n by n matrix over the field with 2 elements with the condition that 'qqi, j, k, l qq {0, 1, ..., n - 1}, i + j = k + l implies a i,j = a k,l' then with a 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 δ.