非表示:
キーワード:
-
要旨:
This thesis consists of two independent parts. In the rst part of the thesis,
we develop a Riemann-Roch theory for sublattices of the root lattice An
extending the work of Baker and Norine (Advances in Mathematics, 215(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 An. 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 fiixed
number of vertices, in particular with running time 2O(n log n)poly(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 nave sampling algorithm.
