Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
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
2015.
Series
TRITA-MAT-E
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-161067OAI: oai:DiVA.org:kth-161067DiVA: diva2:793555
Subject / course
Mathematics
Educational program
Master of Science - Mathematics
Supervisors
Examiners
Available from: 2015-03-10 Created: 2015-03-08 Last updated: 2015-03-10Bibliographically approved

Open Access in DiVA

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

By organisation
Mathematics (Div.)
Mathematics

Search outside of DiVA

GoogleGoogle Scholar
Total: 174 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

urn-nbn

Altmetric score

urn-nbn
Total: 164 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf