Lower bounds for linear decision trees with bounded weights

In this paper, we consider a linear decision tree such that a linear threshold function at each internal node has a bounded weight: the sum of the absolute values of its integer weights is at most w. We prove that if a Boolean function f is computable by such a linear decision tree of size (i.e., the number of leaves) s and rank r, then f is also computable by a depth-2 threshold circuit containing at most s(2w+1)^r threshold gates with weight at most (2w+1)^r+1 in the bottom level. Combining a known lower bound on the size of depth-2 threshold circuits, we obtain a 2^{Ω(n/ logw)} lower bound on the size of linear decision trees computing the Inner-Product function modulo 2, which improves on the previous bound 2^√n if w = 2^o(√n).