The following is a list of potential small research projects in theoretical computer science for MSc students, e.g. for the course DD2467 Individual Project in Theoretical Computer Science.
If you are interested in doing any of these, contact me (Per Austrin) for further discussion.
Some of the paper links below may be to journal versions that are behind pay-walls. These should be freely accessible if you are on the KTH network, but if you are not it is possible to find freely available versions of the respective paper on other sites by a simple search.
Projects are listed in no particular order and additional projects will hopefully be added soon.
The V Label Cover Conjecture asserts that a certain problem called "V Label Cover" is very hard to approximate, and it is known that if this conjecture is true then strong hardness of approximation results for several important problems would follow. The conjecture itself is not very explored, and the purpose of this project would be to look for algorithms to better understand or maybe even disprove the conjecture.
Further reading:
This list just a historical record.
There are many different algorithms for the Subset Sum problem, depending on the characteristics of instances. The most important open question here is whether the classic "meet-in-the-middle" (MitM) algorithm, with running time O(2^{n/2}), can be improved. There are many different algorithms that run faster than MitM for specific instances such as random instances or instances with significant arithmetic structure, and it is rather unclear what are "hard" instances (that are not solved well by any of the existing algorithms). The purpose of this project is to produce a good overview of all the existing algorithms and in the process understand and attempt to construct new hard instances.
Further reading:
In the Max-DiCut problem we get a directed graph, and the goal is to partition the vertices into two parts S and T, such that the number of edges going from S to T is maximized. In the "...with cardinality constraints" variant of the problem, we are additionally given a specified size of S and T. The best current approximation algorithm for this problem has an approximation ratio of 1/2 which is significantly worse than many related problems.
Further reading: