About this course

The purpose of this course is to let you delve deep into some topic you are interested in within the field of theoretical computer science. This is done by doing a small research project under the guidance of a faculty member.

Since the course is done individually, it has no scheduled activities. As such, the course can be started and taken at any time during the year.

The examiner is Douglas Wikström.

Scope and Topics

The project can in principle be within any sub-field of theoretical computer science (e.g. algorithms, complexity theory, cryptography, or formal methods) as long as there is some available faculty member with expertise in the subject.
The project should be grounded in the state of the art of current research in its area. In general, the 7.5 credit scope of the course is not sufficiently large to solve any open research problems, and this is not expected of you. Rather, depending on the difficulty of the research area, suitable objectives may be:
- To produce a survey of a specific research problem or subarea (in particular in areas where the state of the art is scattered across many papers and there is a lack of overview).
- To understand and produce an alternative exposition of some breakthrough result (in particular if the original paper is difficult to read).
- Empirical evaluation of different state-of-the-art algorithms for a problem.
- Suggest a new formal model / problem / algorithm and prove some properties about it.
Since the course is the culmination of the Theoretical Computer Science track of the Master Program in Computer Science, it is expected that the project builds upon and dives deeper into material that you learned in the courses of the track:

Getting started

The first step is to find a supervisor and a project.
1. Think about what topics in theoretical computer science you are most interested in and would like to immerse yourself in. Maybe you only have a broad idea (e.g. "I would like to go more in-depth in formal methods"), or maybe you have a more specific idea (e.g. "I would like to study algorithms for matrix multiplication"), or something in between.
2. Identify which faculty member/members work on those topics and could be a suitable supervisor. Perhaps you already know who they are based on having taken courses with them, but if you are unsure and would like guidance, contact examiner who can help put you in contact with a supervisor.
3. Discuss possible projects with the supervisor and/or examiner. If you already have something very specific in mind this is more of a discussion about whether your idea is feasible, and if you more have a broad idea about what types of topics you would like to work on, the supervisor and/or examiner will try to help you narrow it down to a specific project.
Once you have a supervisor and concrete project, write a short project plan.
1. The project plan should briefly outline what you plan to do in the project, have a few references to the primary earlier work that you are basing the project off, indicate what the deliverables of the project will be (see FAQ below), and have a tentative timeline. It does not have to be more than a page long.
2. Send the project plan to the examiner for approval.

Written Report

The report should be written in the style of a research paper in the field.
The intended audience of the written report are your fellow students on the theoretical computer science track.
Example reports:
Here are some examples of reports from good projects from earlier years.
- Simple Parallel Minimum Cuts in Near-Linear Work and Low Depth by Andrés López Martı́nez
- The Ring Learning with Errors Problem by David Balbás Gutiérrez
- Unified Collections by Anders Ågren Thuné

FAQ

Q: What should the deliverables of the project be?
A: the default is that you produce a written report documenting your project (written in the style of a scientific paper) and give a short presentation.
Q: What determines my grade in the course?
A: The grade is decided by your written report and oral presentation, with the written report being the main deciding factor. Within the written report, the technical contents and overall writing quality weigh equally heavy.
Q: Is there any deadline for when my project needs to be finished?
A: From the point of view of the course there is no strict deadline. However you may of course be subject to external deadlines such as not being allowed to start your Master's Thesis until you have finished this course.

Project Ideas

We encourage you to come up with your own proposal, but a few proposals are given below.

Project on Opinion Formation in Social Networks (SN). During the last two decades, online social networks (OSNs) have become ubiquitous parts of modern societies. While initially people expected that this will lead to very positive effects on societies, with better spreading of information and closer connections between friends, we have also seen that OSNs have been abused by malicious actors, who wish to spread misinformation and who aim to increase the polarization in societies. To understand such phenomena from a theoretical point of view, computer scientists started combining opinion formation models from sociology with abstractions of how OSNs impact this process. Based on these abstractions, several papers defined combinatorial and convex optimization problems to mitigate the adverse effects of OSNs. This project will consist of a literature review and potentially novel proofs for such problems, as well as practical simulations; the concrete topic will be picked in accordance with the student. It will require a good background on the theory of algorithms and linear algebra.
Project on Finding Communities in Graphs (SN). Finding communities in graphs is a well-studied problem in several fields of computer science and has applications, for instance, in finding communities in social networks or in finding servers in a datacenter that frequently communicate with each other. Typically these problems are studied using beyond worst-case assumptions, such as random graphs or planted communities, to make the problem tractable from a theoretical point of view. This project will consist of a literature review and potentially novel proofs for such problems, as well as practical simulations; the concrete topic will be picked in accordance with the student. It will require a good background on the theory of algorithms and linear algebra.
Project on Quantum computers (JH). Quantum computers have attracted significant attention lately, both in theory and practice. Various claims are made of hardware being constructed around the world. Claims are usually about practice but to reason about them theory is often useful. There are of many related questions to be considered in detail and here are some possibilities. Depending on time and preliminary findings, a project can focus on any subset of them.
1. How do you distinguish a quantum computation from a randomized computation? Understand the theory behind this and find out
  which machines under construction have been verified to be quantum.
2. There have been claims about "quantum supremacy". In other words the claim that a computation has been made by a quantum computer that cannot be reproduced by any current computer using classical physics. These claims has been disputed. Investigate this controversy.
3. A usual claim by entities constructing a quantum computer is that they have a large number of quantum bits (qbits). There are many other parameters of a quantum computer. What type of operations can be done? Can all qbits interact with each other? For how long can the system be in a quantum state without the state deteriorating.
4. Error correction for quantum computers will probably be very important. Understand what it means to be a quantum error correcting code in theory and try to get an understanding practical problems of constructing them in practice.
Knowledge-Based Strategies for Multi-Agent Games (DG). In a multi-player game, a coalition of players (also called agents) is attempting to achieve an objective within a potentially hostile environment, considered to be the opponent. Solving such a game means to find a strategy that achieves the objective regardless of the moves of the environment. Rescue missions involving robots and humans or pursuit-evasion games are examples of such games. An interesting, but complicating circumstance is when the players have limited information about the current state of affairs, say
due to limited observation capabilities. Such games are called games of imperfect information. The present project investigates the modelling of such games, as well as algorithmic techniques for strategy synthesis. In particular, the project focuses on strategies based on the notion of knowledge. In the context of this project, knowledge refers to information, structured suitably, stored and updated during the course of a play, for deciding on a course of action. Especially interesting is higher-order knowledge, where players maintain and use during play knowledge about the other
players knowledge.
Per Austrin has a list of project ideas: https://www.csc.kth.se/~austrin/projects.html

Suggested by:

DG = Dillian Gurov, dilian@kth.se
JH = Johan Håstad, johanh@kth.se
SN = Stefan Neumann, neum@kth.se