Home

Eigenvectors in graph theory and related problems in numerical linear algebra
(May 5 - 9, 2014)


CLICK HERE TO PARTICIPATE
Review of applications will begin on December 15, 2013
Organizing Committee
  • Anna Gilbert
    (University of Michigan)
  • Peter Jones
    (Yale University)
  • Gunnar Martinsson
    (University of Colorado at Boulder)
  • Van Vu
    (Yale University)

 

Patent(s) Pending & Copyright © Lumeta Corporation 2000-2013. All Rights Reserved. LUMETA, LUMETA Logo, IPSONAR and the IPSONAR logo are the trademarks and service marks of Lumeta Corporation.
Description

The analysis of problems modeled by large graphs is greatly hampered by a lack of efficient computational tools. The purpose of the workshop is to explore possibilities for designing appropriate computational methods that draw on recent advances in numerical methods and scientific computation. Specifically, the questions of how to form the matrices representing graph Laplacians, and how to compute the leading eigenvectors of such matrices will be addressed. It seems likely that these problems will be amenable to algorithms based on randomized projections that dramatically reduce the effective dimensionality of the underlying problems. Such techniques has recently proven highly effective for the related problems of how to find approximate lists of nearest neighbors for clouds of points in high dimensional spaces, and for constructing approximate low-rank factorizations of large matrices. In both cases, a key observation is that the problem of distortions of distances that is inherent to randomized projection techniques can be overcome by using the randomized projections only as pre-conditioners; they inform the algorithm of where to look, and then highly accurate deterministic techniques are used to compute the actual output. The resulting algorithms scale extra-ordinarily well on modern parallel and multicore architectures. To successfully address the enormous problems arising in the analysis of graphs, it is expected that additional machinery will be needed, such as the use of multi-resolution data structures, and more efficient scalable randomized projections.


  • Sanjeev Arora
    (Princeton University)
  • John Augustine
    (Indian Institute of Technology)
  • Chen Avin
    (Ben Gurion University of the Negev)
  • Devasis Bassu
    (Applied Communication Sciences)
  • Daniel Bienstock
    (Columbia University)
  • Milan Bradonjic
    (Bell Labs, Alcatel-Lucent)
  • Lawrence Carin *
    (Duke University)
  • Yanlai Chen
    (University of Massachusetts)
  • Fan Chung*
    (University of California, San Diego)
  • Raphy Coifman*
    (Yale University)
  • Thomas Dickerson
    (Brown University)
  • Ioana Dumitriu*
    (University of Washington)
  • Kyle Fox
    (University of Illinois at Urbana-Champaign)
  • Eli Fox-Epstein
    (Brown University)
  • Nathanaël François
    (Université de Paris VII (Denis Diderot))
  • Rong Ge *
    (Microsoft Research)
  • Anna Gilbert *
    (University of Michigan)
  • Venu Gopal
    (Brown University)
  • Steven Heilman
    (Courant Institute of Mathematical Sciences)
  • Jeremy Hoskins
    (University of Michigan)
  • Peter Jones*
    (Yale University)
  • Philip Klein
    (Brown University)
  • Andrew Knyazev
    (Mitsubishi Electric Research Laboratories)
  • Yiannis Koutis
    (University of Puerto Rico)
  • Roy Lederman
    (Yale University)
  • James Lee*
    (University of Washington)
  • Gilad Lerman*
    (University of Minnesota)
  • Gabor Lippner
    (Harvard University)
  • Mauro Maggioni*
    (Duke University)
  • Ahmad Mahmoody
    (Brown University)
  • Michael Mahoney *
    (Stanford University)
  • William Martin
    (Worcester Polytechnic Institute)
  • Gunnar Martinsson*
    (University of Colorado)
  • David Meierfrankenfeld
    (Brown University)
  • Ankur Moitra*
    (Massachusetts Institute of Technology)
  • Nathan Monnig
    (University of Colorado Boulder)
  • Jason Morton
    (Pennsylvania State University)
  • Elchanan Mossel *
    (University of California, Berkeley)
  • Danupon Nanongkai
    (Nanyang Technological University)
  • Joe Neeman *
    (University of Texas at Austin)
  • Linda Ness
    (Applied Communication Sciences)
  • Hoi Nguyen
    (The Ohio State University)
  • Sean O'Rourke*
    (Yale University)
  • Andrei Osipov*
    (Yale University)
  • Gopal Pandurangan
    (Nanyang Technological University)
  • Saad Quader
    (University of Connecticut)
  • Ben Raphael
    (Brown University)
  • Amanda Redlich
    (Bowdoin College)
  • Igor Rivin
    (Temple University)
  • Scott Roche
    (Northeastern University)
  • Vladimir Rokhlin*
    (Yale University)
  • Mark Rudelson*
    (University of Michigan)
  • Amit Singer *
    (Princeton University)
  • Giulio Tiozzo
    (Harvard University)
  • Charalampos Tsourakakis
    (Carnegie Mellon University)
  • Eli Upfal
    (Brown University)
  • Sergey Voronin
    (University of Colorado)
  • Van Vu*
    (Yale University)
  • Ke Wang*
    (University of Minnesota)
  • Rachel Ward *
    (University of Texas at Austin)
  • Rebecca Willett *
    (University of Wisconsin)
  • Grigory Yaroslavtsev
    (Pennsylvania State University)
  • Xiangxiong Zhang
    (Massachusetts Institute of Technology)