Organizing Committee
Abstract

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.

Image for "Eigenvectors in graph theory and related problems in numerical linear algebra"
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.

Confirmed Speakers & Participants

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, May 5, 2014
TimeEventLocationMaterials
8:30 - 8:55am EDTRegistration11th Floor Collaborative Space 
8:55 - 9:00am EDTWelcome - ICERM Director11th Floor Lecture Hall 
9:00 - 9:45am EDTEigenvectors, Heat Kernels, and Low Dimensional Representation of Data Sets - Peter Jones, Yale University11th Floor Lecture Hall
9:50 - 10:35am EDTMultiscale Geometric Methods for Statistical Learning and Data in High-Dimensiona - Mauro Maggioni, Duke University11th Floor Lecture Hall
10:40 - 11:10am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:10 - 11:55am EDTTracking Influences within Dynamic Networks - Rebecca Willett, University of Wisconsin11th Floor Lecture Hall
12:00 - 2:00pm EDTLunch Break and Free Time  
2:00 - 2:45pm EDTRobust and Fast Subspace Recovery - Gilad Lerman, University of Minnesota11th Floor Lecture Hall
2:50 - 3:35pm EDTRandomized Algorithms in DNA Sequencing - Roy Lederman, Yale University11th Floor Lecture Hall 
3:40 - 4:10pm EDTCoffee Break11th Floor Collaborative Space 
4:10 - 4:55pm EDTDiffuse Scattering on Graphs and Combinatorial Inverse Problems - Anna Gilbert, University of Michigan11th Floor Lecture Hall
5:00 - 6:30pm EDTWelcome Reception11th Floor Collaborative Space 
Tuesday, May 6, 2014
TimeEventLocationMaterials
9:00 - 9:45am EDTCovariance Matrix Estimation for the Cryo-EM Heterogeneity Problem - Amit Singer, Princeton University11th Floor Lecture Hall
9:50 - 10:35am EDTA randomized approximate nearest neighbors algorithm - Andrei Osipov, Yale University11th Floor Lecture Hall
10:40 - 11:10am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:10 - 11:55am EDTEigenvector localization, implicit regularization, and algorithmic anti-differentiation for large-scale graphs and networked data - Michael W. Mahoney, University of California, Berkeley11th Floor Lecture Hall
12:00 - 2:00pm EDTLunch Break and Free Time  
2:00 - 2:45pm EDTTBA - Vladimir Rokhlin, Yale University11th Floor Lecture Hall 
2:50 - 3:35pm EDTGaps in eigenfunctions of Graphs - Fan Chung, University of California, San Diego11th Floor Lecture Hall
3:40 - 4:10pm EDTCoffee Break11th Floor Collaborative Space 
4:10 - 4:55pm EDTInverse problems on random graphs and censored block models - Emmanuel Abbe, Princeton University11th Floor Lecture Hall 
Wednesday, May 7, 2014
TimeEventLocationMaterials
9:00 - 9:45am EDTNew Algorithms for Learning Incoherent and Overcomplete Dictionaries - Rong Ge, Microsoft Research11th Floor Lecture Hall
9:50 - 10:35am EDTA threshold for reconstruction in stochastic block models - Joe Neeman, University of Texas at Austin11th Floor Lecture Hall
10:40 - 11:10am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:10 - 11:55am EDTNetwork Clustering, the Block Stochastic Model, and a Regular Graph - Ioana Dumitriu, University of Washington11th Floor Lecture Hall
12:00 - 12:05pm EDTGroup Photo11th Floor Lecture Hall 
12:05 - 2:00pm EDTLunch Break and Free Time  
2:00 - 2:45pm EDTDimension reduction in the l1 norm- When and how is it possible - Rachel Ward, University of Texas at Austin11th Floor Lecture Hall
2:50 - 3:35pm EDTRandom weighted projections, random quadratic forms and random eigenvectors - Ke Wang, University of Minnesota11th Floor Lecture Hall
3:40 - 4:10pm EDTCoffee Break11th Floor Collaborative Space 
4:10 - 4:55pm EDTSpectral algorithms for graph mining and analysis - Yiannis Koutis, University of Puerto Rico11th Floor Lecture Hall
7:00 - 8:30pm EDTPoster Session and Dessert Reception11th Floor Collaborative Space 
Thursday, May 8, 2014
TimeEventLocationMaterials
9:00 - 9:45am EDTInformation-theoretic learned linear projections for dimensionality reduction - Lawrence Carin, Duke University11th Floor Lecture Hall
9:50 - 10:35am EDTA Polynomial Time Algorithm for Lossy Population Recovery - Ankur Moitra, Massachusetts Institute of Technology11th Floor Lecture Hall
10:40 - 11:10am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:10 - 11:55am EDTPermanent estimators via random matrices - Mark Rudelson, Univeristy of Michigan11th Floor Lecture Hall
12:00 - 2:00pm EDTLunch Break and Free Time  
2:00 - 2:45pm EDTA simple spectral algorithm for a general clustering problem - Van Vu, Yale University11th Floor Lecture Hall
2:50 - 3:35pm EDTRandom perturbation of low rank matrices- Improving classical bounds - Sean O'Rourke, Yale University11th Floor Lecture Hall
3:40 - 4:10pm EDTCoffee Break11th Floor Collaborative Space 
4:10 - 4:55pm EDTIs Belief Propagation a Spectral algorithm - Elchanan Mossel, University of California, Berkeley11th Floor Lecture Hall
Friday, May 9, 2014
TimeEventLocationMaterials
9:50 - 10:35am EDTPanel Summary - Panel Discussion Chair: Anna Gilbert, University of Michigan11th Floor Lecture Hall 
10:30 - 11:00am EDTCoffee/Tea Break11th Floor Collaborative Space 
11:10 - 11:55am EDTPanel Summary11th Floor Lecture Hall 
12:00 - 5:00pm EDTAfternoon Free for Collaborations  

Associated Semester Workshops

Network Science and Graph Algorithms
Image for "Network Science and Graph Algorithms"
Semidefinite Programming and Graph Algorithms
Image for "Semidefinite Programming and Graph Algorithms"
Stochastic Graph Models
Image for "Stochastic Graph Models"

Research Clusters

Lecture Videos