Change search
ReferencesLink to record
Permanent link

Direct link
Topological Lower Bounds in Complexity Theory
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).
2015 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesisAlternative title
Topologiska undre gränser i komplexitetsteori (Swedish)
Abstract [en]

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).

Place, publisher, year, edition, pages
National Category
URN: urn:nbn:se:kth:diva-161067OAI: diva2:793555
Subject / course
Educational program
Master of Science - Mathematics
Available from: 2015-03-10 Created: 2015-03-08 Last updated: 2015-03-10Bibliographically approved

Open Access in DiVA

fulltext(674 kB)96 downloads
File information
File name FULLTEXT01.pdfFile size 674 kBChecksum SHA-512
Type fulltextMimetype application/pdf

By organisation
Mathematics (Div.)

Search outside of DiVA

GoogleGoogle Scholar
Total: 96 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 134 hits
ReferencesLink to record
Permanent link

Direct link