AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI   Info

AG Audience

English

45 Minutes

Saarbrücken

The talk will start with a brief introduction to the basic notions of the Riemann-Roch theory for graphs developed by Baker and Norine(Advances in Mathematics, 215(2): 766-788, 2007). Key elements in the theory are the concept of rank of a configuration and a duality theorem that plays an important role in the proof of the Riemann-Roch theorem. We will then discuss algorithmic and complexity results on the problem of computing the rank of a configuration and also simultaneously demonstrate the central role played by the duality theorem in these results. Motivated by the problem of determining the inherent computational complexity of rank, We will sketch generalisations of the duality theorem. The generalisation involves a new way to capture the symmetries of a graph. We will conclude the talk with some related open problems.

Madhusudan Manjunath

--email hidden

passcode not visible

logged in users only

Graphs, Lattices, distance functions