English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  A Riemann-Roch Theory for Sublattices of the Root Lattice A n, Graph Automorphisms and Counting Cycles in Graphs

Manjunath, M. (2011). A Riemann-Roch Theory for Sublattices of the Root Lattice A n, Graph Automorphisms and Counting Cycles in Graphs. PhD Thesis, Universität des Saarlandes, Saarbrücken.

Item is

Basic

show hide
Genre: Thesis
Latex : A {R}iemann-{R}och Theory for Sublattices of the Root Lattice A n, Graph Automorphisms and Counting Cycles in Graphs

Files

show Files

Locators

show
hide
Description:
-
OA-Status:
Green
Locator:
http://scidok.sulb.uni-saarland.de/doku/lic_ohne_pod.php?la=de (Copyright transfer agreement)
Description:
-
OA-Status:
Not specified

Creators

show
hide
 Creators:
Manjunath, Madhusudan1, 2, Author           
Mehlhorn, Kurt2, Advisor           
Haase, Christian3, Referee
Affiliations:
1International Max Planck Research School, MPI for Informatics, Max Planck Society, ou_1116551              
2Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
3External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2011-12-202011
 Publication Status: Issued
 Pages: -
 Publishing info: Saarbrücken : Universität des Saarlandes
 Table of Contents: -
 Rev. Type: -
 Identifiers: BibTex Citekey: ManjunathPhd2011
DOI: 10.22028/D291-26350
URN: urn:nbn:de:bsz:291-scidok-47818
Other: hdl:20.500.11880/26406
 Degree: PhD

Event

show

Legal Case

show

Project information

show

Source

show