General project flavors

Overview

Who is this document for?

This document is intended for students at Goethe University who are considering to write a Bachelor/Master thesis in the theoretical computer science group and want to find a topic.

Project Types

Depending on your interests and talents, different types of projects are possible:

Often, there is some overlap between different types.

Implementation and Experimentation

In this type of project, you will:

Literature review

In this type of project, you will choose a topic in theoretical computer science and write a literature review of existing research on this topic. This involves tracking down as many relevant papers and preprints on the topic as feasible, reading and understanding them, identifying the most important results as well as the most important open problems and goals of the research direction, and writing a comprehensive report. A project with a more limited scope could be to rewrite a specific proof from a research paper.

Problem-solving

In this type of project, you will prove new theorems in theoretical computer science. This could be upper bounds (algorithms, data structures) or lower bounds (hardness reductions, complexity). A project with a limited scope would be to analyze the proof of an existing theorem in a special case, and write it up as elegantly as possible. Problem-solving projects are much more challenging than a typical thesis project.

Themes and Topics

Depending on your interests and talents, different themes of project topics are possible: Theory, Engineering, Visualization, and AI Alignment.

Theory

Goal: perform a literature review or solve open problems in theoretical computer science.

What you get out of it:

What you need to bring:

Algorithmic Engineering

Goal: implement algorithms that may have never been implemented before! Test them rigorously, and compare their performance to other algorithms and implementations.

What you get out of it:

What you need to bring:

More specific aspects of a possible projects:

Software and benchmarks generated in your projects are developed under an open-source license, and when they’re ready will be published in a suitable outlet.

Visualization of Algorithmic Concepts

Goal: develop beautiful and easy-to-use educational visualizations of algorithmic and mathematical concepts. Make no mistake, the project should still include scientific writing in the form of a comprehensive Bachelor or Master thesis that describes the topic on a formal level, reviews the literature (both of the concept involved and its possibly pre-existing visualizations), discusses some experiments (maybe with different possible visualization and interaction patterns), and justifies your choices.

Examples: Past projects that are at the level of a Bachelor thesis include Algorithms with Albot, Color Refinement, and Graph Width Visualizer.

Non-examples: Your visualization project should do something new. For example, visualizing different sorting algorithms has been done before (a lot), so if that’s your proposal, you need to provide a very strong argument why your visualization idea is novel.

What you get out of it:

What you need to bring:

Since I want the results of visualization projects to be as accessible as possible, the applications will be browser-based and therefore use JavaScript (or a suitable other language, such as Python, in combination with WebAssembly). All products generated in your projects are developed under an open-source license, and when they’re ready will be publicly available.

More specific aspects of possible projects:

Links to existing visualization projects.

Human-aligned artificial intelligence

Goal: perform a literature review, or contribute to original research on the alignment problem. In particular, I would be most interested in connections to traditional, technical topics in theoretical computer science (algorithms, complexity, game theory, logics, cryptography). Topics such as “safe machine learning” are also possible.

What you get out of it:

What you need to bring:

Some introductory resources: