DD2467 HT23 Individual Project in Theoretical Computer Science (tcsindh23)

Course Information

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

 

Getting started

  1. 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.
  2. 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

 

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

Public Domain This course content is offered under a Public Domain Links to an external site. license. Content in this course can be considered under this license unless otherwise noted.