# Open for applications

Research project in

Algebraic Complexity Theory and Combinatorics

(Mathematics and Theoretical Computer Science)

(Including Summer internship position in Germany)

Prof. Radu Curticapean, University of Copenhagen, Denmark

Prof. Cornelius Brand, Regensburg University, Germany

Number of positions: 2.

Deadline: 05 Feb 2024.

This project includes an internship phase in Germany this summer funded by the mentors.

Depending on the progress, a Ph.D. position might be offered.

Detailed information can be found below.

Application: Fill in the form here.

Description.

Studying the interplay between algebraic and combinatorial objects has proven extremely useful and productive, e.g., in algebraic complexity theory [1] and the theory of graph homomorphisms [3, 4]. Many important matrix polynomials, such as the determinant or the permanent, have combinatorial reinterpretations, e.g., as (weighted) enumerations of cycle covers in directed graphs. Conversely, polynomials derived from graph homomorphisms form a specific generating set of the invariant ring of Sn × Sn, which endows algebraic objects with new combinatorial meaning.

Going back and forth between these two points of view allows us to deduce new insights both about the algebraic objects (polynomials), as well as their combinatorial counterparts (graph homomorphisms). Even more, it is possible to gain insight about the computational complexity of combinatorial problems (such as counting cycle covers) through purely algebraic quantities. Most important in this context are various notions of rank that can be associated with tensors or polynomials [2] In this project, we will explore several related questions on objects arising in the combinatorial context of graph homomorphisms.

Goals:

The goals of this project are to become proficient in algebraic complexity theory and understand precisely the main questions of the area, and then make progress on one or more specific questions related to the topics outlined above, depending on the preferences and background of the student. Specifically, we are interested in the (symmetric) tensor rank of certain (symmetric) tensors that arise in the context of the subgraph isomorphism problem, which are intimately related to the complexity of matrix multiplication and combinatorial problems. In a more abstract vein, we are also interested in combinatorial interpretations of the coefficient sequences of polynomials when expanded in bases that carry combinatorial structure.

Prerequisites:

We are looking for students with strong background in algebra or adjacent fields. In particular, we do not assume significant background in theoretical computer science

Outlook:

In case of progress, this project can be the entry point for a graduate-level thesis, and possibly for a PhD dissertation at the University of Regensburg, Germany.

References

[1] Peter B¨urgisser, Michael Clausen, and Mohammad Amin Shokrollahi. Algebraic complexity theory. Vol. 315. Grundlehren der mathematischen Wissenschaften. Springer, 1997. isbn: 3-540-60582-7.

[2] Joseph M Landsberg. Tensors: geometry and applications: geometry and applications. Vol. 128. American Mathematical Soc., 2011.

[3] Laszlo Lov´asz. Large networks and graph limits. Vol. 60. American Mathematical Soc., 2012.

[4] Laszlo Lovasz. “Operations with structures”. In: Acta Mathematica Hungarica, 18.3-4 (1967), pp. 321–328.