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

Difficult point conjecture for graph polnomials:

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.

Polynomials with small circuits but many integer roots:

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:
Markus Bläser, Julian Dörfler, Christian Ikenmeyer.
On the Complexity of Evaluating Highest Weight Vectors
Proc. of the 36th Computational Complexity Conference (CCC 2021), LIPIcs 200, 29:1-29:36, 2021.

2013

Thatchaphol Saranurak

PosSLP and the monotone complexity of computing integers.
Master’s Thesis.
Advisor: Markus Bläser

Corresponding publication:
Thatchaphol Saranurak and Gorav Jindal
Subtraction makes computing integers faster.
CoRR abs/1212.2549 (2012)

Gorav Jindal

Randomness efficient testing of sparse blackbox polynomials and relatex tasks.
Master’s Thesis.
Advisor: Markus Bläser

Corresponding publication:
Markus Bläser, Gorav Jindal
A new deterministic algorithm for sparse multivariate polynomial interpolation
Proc. of the Int. Symp. on Symbolic and Algebraic Computation (ISSAC 2014), 51-58, 2014.

2012

Marvin Künnemann

A Quantization Framework for Smoothed Analysis on Euclidean Optimization Problems.
Master’s Thesis.
Advisor: Radu Curticapean

Corresponding publication:
Radu Curticapean, Marvin Künnemann
A Quantization Framework for Smoothed Analysis of Euclidean Optimization Problems.
Proc. of the 21st European Symp. on Algorithms (ESA), LNCS 8125, 349-360 , 2013.
ESA best student paper award

2011

Radu Curticapean.

Holographic algorithms.
Master’s Thesis.
Advisor: Markus Bläser

Corresponding publication:
Markus Bläser, Radu Curticapean
The Complexity of the Cover Polynomials for Planar Graphs of Bounded Degree.
Proc. of the 36th Int. Symp. on Mathematical Foundations of Computer Science (MFCS), LNCS 6907, 96-107, 2011.

2010

Christian Engels

Polynomial Identity Testing.
Master’s Thesis.
Advisor: Markus Bläser

Corresponding publication:
Markus Bläser, Christian Engels
Randomness Efficient Testing of Sparse Black Box Identities of Unbounded Degree over the Reals.
Proc. of the 28th Symp. on Theoretical Aspects of Computer Science (STACS), LIPIcs 9, 555-566, 2011.

2008

Nima Zeini Jahromi

Smoothed Analysis of Quicksort with Median-Of-Three Pivot Rule.
Bachelor’s Thesis.
Advisor: Bodo Manthey

Corresponding publication:
Mahmoud Fouz, Manfred Kufleitner, Bodo Manthey, Nima Zeini Jahromi
On Smoothed Analysis of Quicksort and Hoare’s Find.
Proc. of the 15th Int. Computing and Combinatorics Conference (COCOON 2009), LNCS 5609, 158-167. Springer, 2009.

Christian Engels

Probabilistic Analyses of Algorithms for the TSP.
Bachelor’s Thesis.
Advisor: Bodo Manthey

Corresponding publication:
Christian Engels, Bodo Manthey
Average-Case Approximation Ratio of the 2-Opt Algorithm for the TSP.
Operations Research Letters, 37(2):83-84, 2009

2007

Holger Dell	Complexity of the Cover Polynomial. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: Markus Bläser, Holger Dell Complexity of the Cover Polynomial. Proc. of the 34th Int. Coll. on Automata, Languages and Programming (ICALP 2007) , LNCS 4596, 801-812, 2007.
Oliver Putz	Approximation Algorithms for the Multi-criteria MAX TSP Problem. Bachelor’s Thesis. Advisor: Markus Bläser Corresponding publication: Markus Bläser, Bodo Manthey, Oliver Putz Approximating Multi-Criteria Max-TSP. Proc. of the 16th European Symp. on Algorithms (ESA 2008), LNCS 5193, 185-197, 2008.
Moritz Hardt	Testing Polynomial Identities with Fewer Random Bits. Master’s Thesis. Advisor: Markus Bläser Corresponding publications: Markus Bläser, Moritz Hardt, David Steurer Asymptotically Optimal Hitting Sets Against Polynomials. Proc. of the 35th Int. Coll. on Automata, Languages and Programming (ICALP 2008), LNCS 5125, 345-356, 2008. Markus Bläser, Moritz Hardt, Richard J. Lipton, Nisheeth K. Vishnoi Deterministically Testing Sparse Polynomial Identities of Unbounded Degree. Information Processing Letters, 109(3):187-192, 2009
Mahmoud Fouz	Inapproximability of the Geometric Cover Polynomial. Master’s Thesis. Advisor: Markus Bläser Corresponding publication: Markus Bläser, Holger Dell, Mahmoud Fouz Complexity and Approximability of the Cover Polynomial. computational complexity, 21(3):359-419, Springer, 2012