Computational Complexity – Bachelor’s and Master’s Theses
If you are interested in doing a thesis in the computational complexity group, please contact any member of the group. Below is only a small sample of possible topics, mainly more general ones which only require basic knowledge in theoretical computer science. Feel free to ask for more topics or suggest a topic of your own. The best way to find an interesting topic is attending a core or advanced lecture offered by us and then asking for a topic towards the end of the lecture.
Suggested Topics
A graph invariant is a function from the set of all graphs into a ring such that isomorphic graphs are mapped to the same value. A graph polynomial is a graph invariant that maps every graph to a polynomial. The most famous graph polynomial is the so-called Tutte polynomial. By substituting values for the variables of the polynomial, we get a family of graph invariants. Makowsky’s difficult point conjecture states that for a certain class of graph polynomials, if one of these points are #P-hard to evaluate, then almost all of them are. The conjecture is still open, but we do not know any counter example to it. There are still many concrete graph polynomials for which the difficult point conjecture has not yet been verified.
The tau conjecture essentially states that polynomials with small arithmetic circuits can only have few integer roots. Astonishingly, it implies the separation of the algebraic analogues of P and NP! Circuits that are particularly efficient were found partially using computer search, see below. Since this was ten years ago and computer technology has advanced quite a bit meanwhile, it might be interesting to search for new examples.
Bernd Borchert, Pierre McKenzie, and Klaus Reinhardt
Few product gates but many zeroes
Chicago Journal of Theoretical Computer Science, 2013:2, 2013
Selected finished theses
Below is a selection of some theses written in our group.
2020
Julian Dörfler | On the complexity of evaluating highest weight vectors. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: |
2013
Thatchaphol Saranurak | PosSLP and the monotone complexity of computing integers. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: |
Gorav Jindal | Randomness efficient testing of sparse blackbox polynomials and relatex tasks. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: |
2012
Marvin Künnemann | A Quantization Framework for Smoothed Analysis on Euclidean Optimization Problems. Master’s Thesis. Advisor: Radu Curticapean Corresponding publication: |
2011
Radu Curticapean. | Holographic algorithms. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: |
2010
Christian Engels | Polynomial Identity Testing. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: |
2008
Nima Zeini Jahromi | Smoothed Analysis of Quicksort with Median-Of-Three Pivot Rule. Bachelor’s Thesis. Advisor: Bodo Manthey Corresponding publication: |
Christian Engels | Probabilistic Analyses of Algorithms for the TSP. Bachelor’s Thesis. Advisor: Bodo Manthey Corresponding publication: |
2007
Holger Dell | Complexity of the Cover Polynomial. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: |
Oliver Putz | Approximation Algorithms for the Multi-criteria MAX TSP Problem. Bachelor’s Thesis. Advisor: Markus Bläser Corresponding publication: |
Moritz Hardt | Testing Polynomial Identities with Fewer Random Bits. Master’s Thesis. Advisor: Markus Bläser Corresponding publications: Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi |
Mahmoud Fouz | Inapproximability of the Geometric Cover Polynomial. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: |