[Dmbu-l] BU Theory Seminar, Monday at 2:00 - Yiannis Koutis on spectral graph sparsification (fwd)

Evimaria Terzi evimaria at bu.edu
Mon May 5 00:07:40 EDT 2014



"Everything should be made as simple as possible, but no simpler"
(A. Einstein)

---------- Forwarded message ----------
Date: Wed, 30 Apr 2014 18:02:11 -0400 (EDT)
From: Steve Homer <homer at cs.bu.edu>
To: Steve Homer <homer at cs.bu.edu>
Subject: BU Theory Seminar,
     Monday at 2:00 - Yiannis Koutis on spectral graph sparsification


                  Monday Theory Seminar

  Yiannis Koutis - University of Puerto Rico and Brown University

Title: Spectral graph sparsification and fast Laplacian solvers

Date: Monday, May 5 at 2:00 in MCS 148

Abstract:

Algorithms for solving linear systems
involving graph Laplacians are now capable of handling graphs with millions of 
edges. They have consequently become an important algorithmic primitive with 
applications in diverse areas. Central to the design of fast solvers is the 
problem of spectral graph sparsification. We describe an extremely simple 
sparsification algorithm, the first to admit an implementation in the 
distributed model. The simplicity of the algorithm provides an opportunity for 
a review of the interplay between combinatorial algorithms and algebra that 
forms the basis of  most recently discovered fast Laplacian solvers.


Bio: Ioannis Koutis is an assistant professor in the Computer Science 
Department at the University of Puerto Rico, Rio Piedras. He holds a PhD in 
Computer Science from Carnegie Mellon University, and a Diploma in Computer 
Engineering and Informatics from the University of Patras, Greece. His research 
interests include algorithmic applications of spectral graph theory, numerical 
computations with provable properties and algebraic algorithms for 
parameterized and exact problems.








More information about the Dmbu-l mailing list