Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, October 27, 2011, 12:15 pm
Duration: 30 minutes
Location: OAT S15/S16/S17
Speaker: Anastasios Zouzias (University of Toronto)
In this talk, we will discuss a generalization of Spencer’s hyperbolic cosine algorithm to the matrix-valued setting. Then, we will apply the proposed algorithm on two graph theoretic problems and obtain fast deterministic algorithms for these problems. That is, we will describe a near-optimal deterministic algorithm that, given the multiplication table of a finite group of size n, constructs an Alon-Roichman expanding Cayley graph of logarithmic degree in O(n2 log3 n) time. Second, we will give a fast deterministic algorithm for spectral graph sparsification of dense graphs building on the work of Spielman and Srivastava.
Automatic MiSe System Software Version 1.4803M | admin login