On the Space and Circuit Complexity of Certain Parameterized Problems.

Max Bannach


Parameterized complexity theory provides important tools to generate and an- alyze reasonable fast algorithms for hard problems. Current research mainly focuses on the question whether parameterized problems are fixed-parameter tractable or not, i. e., if there is a fast algorithm solving them. Thus, the only considered resource is time, while parameterized space and circuit complexity is often omitted, although these resources are useful in classical complexity the- ory as well. A recent work from Elberfeld, Stockhusen, and Tantau provides a framework of parameterized space and circuit classes to cover this area [26]. Al- though the framework provides parameterized space and circuit classes, as well as tools to analyze them, there is still a lack of complete problems for most of these classes. The objective of this thesis is to resolve this issue by analyzing widely known problems with respect to the framework and, thus, populate the different classes. This will lead to new upper bounds for many natural prob- lems, together with a couple of new lower bounds for some of them. Moreover, we will also be able to collide the upper and lower bounds of some of these problems and, hence, finally resolve the complexity of them
Original languageEnglish
QualificationMaster of Science
Awarding Institution
  • Tantau, Till, Supervisor
  • Liskiewicz, Maciej, Supervisor
Publication statusPublished - 2014


Dive into the research topics of 'On the Space and Circuit Complexity of Certain Parameterized Problems.'. Together they form a unique fingerprint.

Cite this