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

AG Audience

English

30 Minutes

Saarbrücken

This thesis consists of two independent parts. In the first part of the thesis, we develop a Riemann-Roch theory for sublattices of the root lattice $A_n$ extending the work of Baker and Norine ({\textit Advances in Mathematics}, 215({\textbf 2}): 766-788, 2007) and study questions that arise from this theory. Our theory is based on the study of critical points of a certain simplicial distance function on a lattice and establishes connections between the Riemann-Roch theory and the Voronoi diagrams of lattices under certain simplicial distance functions. In particular, we provide a new geometric approach for the study of the Laplacian of graphs. As a consequence, we obtain a geometric proof of the Riemann-Roch theorem for graphs and generalise the result to other sub-lattices of $A_n$. Furthermore, we use the geometric approach to study the problem of computing the rank of a divisor on a finite multigraph $G$ to obtain an algorithm that runs in polynomial time for a fixed number of vertices, in particular with running time $2^{O(n \log n)}\text{poly}(\text{size}(G))$ where $n$ is the number of vertices of $G$. Motivated by this theory, we study a dimensionality reduction approach to the graph automorphism problem and we also obtain an algorithm for the related problem of counting automorphisms of graphs that is based on exponential sums.

In the second part of the thesis, we develop an approach, based on complex-valued hash functions, to count cycles in graphs in the data streaming model. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the na\"ive sampling algorithm.

Madhusudan Manjunath

--email hidden

passcode not visible

logged in users only