Topological Lower Bounds in Complexity Theory

Abstract: 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/6k).