Erik Larsson: Topological lower bounds in complexity theory

The first goal of this thesis is to present two different methods, originally developed by Björner, Lovász and Yao, for proving lower bounds on the worst-case complexity in the linear decision tree model. The methods are exemplified 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, 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).