AbstractsMathematics

The first goal of this thesis is to present two different methods, originally developed by Björner, Lovász and Yao [4], for proving lower bounds on the worst-case complexity in the linear decision tree model, by applying them to the k -EQUAL PROBLEM. Both methods are based on the computation of topological properties of the intersection lattice of a subspace arrangement. The second goal is to use one of these methods (based on estimates of Betti numbers) to improve upon a lower bound, due to Linusson [12], on the linear decision tree complexity c ′( n,k ) of the k -of-EACH PROBLEM on n elements. We show that c ′( n,k ) ≥ n log₃( n /6 k ).