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

Review of applications will begin on December 15, 2013
Organizing Committee


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.

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
    (Lucent Technologies Bell Laboratories)
  • 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)
  • Risi Kondor
    (University of Chicago)
  • Yiannis Koutis
    (University of Puerto Rico)
  • Roy Lederman
    (Yale University)
  • Gilad Lerman*
    (University of Minnesota)
  • Gabor Lippner
    (Harvard University)
  • Mauro Maggioni*
    (Duke University)
  • Ahmad Mahmoody
    (Brown University)
  • Michael Mahoney *
    (University of California, Berkeley)
  • William Martin
    (Worcester Polytechnic Institute)
  • Gunnar Martinsson*
    (University of Colorado)
  • David Meierfrankenfeld
    (Brown University)
  • Francois Meyer
    (University of Colorado)
  • 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
    (Ohio State University)