Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity




Computational Complexity - Suggested Topics for Theses

Upper bounds and the rank and border rank of small tensors by computer methods

Good upper bounds on the rank (and border rank) of small matrix multiplication tensors are crucial for
designing fast practical algorithms for matrix multiplication. But they are also interesting from the view point
of complexity theory. In the present thesis, one should try to find such upper bounds by means
of computer search. Either by using numerical methods or by using SAT solvers.

Contact: Prof. Dr. Markus Bläser