DIMACS Workshop on Big Data through the Lens of Sublinear Algorithms

August 27 - 28, 2015
DIMACS Center, CoRE Building, Rutgers University

Organizers:: Alexandr Andoni, Columbia University; Muthu Muthukrishnan, Rutgers University, smewtoo at gmail.com; Grigory Yaroslavtsev, University of Pennsylvania, grigory.yaroslavtsev at gmail.com

Presented under the auspices of the DIMACS Special Focus on Information Sharing and Dynamic Data Analysis.

Workshop Program:

Check for the most current version of the program.

Thursday, August 27, 2015

 8:30 -  9:00  Breakfast and Registration

 9:00 - 10:00  Keynote: Streaming Algorithms for Set Cover
               Piotr Indyk, MIT
               Slides  Video

10:00 - 10:15  Coffee Break

10:15 - 12:45  Optimization While Streaming
               Amit Chakrabarti, Dartmouth College
               Slides  Video
    
               Trusting the Cloud with Practical Interactive Proofs
               Graham Cormode, University of Warwick
               Slides  Video

               On Testing Properties in Directed Graphs
               Artur Czumaj, University of Warwick
               Slides  Video

               Palindrome Recognition In The Streaming Model
               Funda Ergun, Indiana University, Bloomington & Simon Fraser University
               Slides  Video
               
               Approximate Matchings in Dynamic Graph Streams
               Sanjeev Khanna, University of Pennsylvania 
               Slides  Video
 
12:45 -  2:05  Lunch Break

 2:05 -  2:15  Tami Carpenter, Rutgers University, DIMACS
               DIMACS Welcome

 2:15 -  3:15  Tutorial: A Survey of Results in the Message Passing Communication Model
               David Woodruff, IBM Research, Almaden
               Slides  Video

 3:15 -  3:30  Coffee Break

 3:30 -  6:00  The Power of Randomization: Distributed Submodular Maximization on Massive Datasets
               Alina Ene, University of Warwick
               Slides  Video

               Expanders via Local Edge Flips
               Silvio Lattanzi, Google Research, NYC
               Slides  Video
      
               Linear and Sublinear Aspects of Combining SGD and RLA
               Michael Mahoney, University of California, Berkeley
               Slides  Video

               Large-scale Graph Mining at Google NYC: Problems and Frameworks       
               Vahab Mirrokni, Google Research, NYC
               Slides  Video
     
               Communication Complexity of Learning Discrete Distributions               
               Krzysztof Onak, IBM Research, NY
               Slides  Video
     
 6:00 -  8:00  Dinner + Poster Session 

Friday, August 28, 2015

 8:30 -  9:00  Breakfast and Registration

 9:00 - 10:00  Keynote: Sublinear Algorithms for PageRank, with Applications 
               Ashish Goel, Stanford University
               Slides   Video

10:00 - 10:30  Coffee Break

10:30 - 11:30  Tutorial: Graph Connectivity in MapReduce: How Hard Could it Be?
	       Sergei Vassilvitskii, Google Research, NYC

11:30 - 12:30  An Introduction to Chaining, and Applications to Sublinear Algorithms
               Jelani Nelson, Harvard University
               Slides   Video

               Testing and Correcting Structured Distributions
               Ronitt Rubinfeld, MIT
               Slides   Video

12:30 -  2:00  Lunch Break

 2:00 -  3:00  Keynote: Logarithic Time Prediction
               John Langford, Microsoft Research, NYC
               Slides   Video

 3:00 -  3:30  Coffee Break

 3:30 -  6:30  Efficient Primal-dual Graph Algorithms on MapReduce
               Kamesh Munagala, Duke University
               Slides   Video

               Distributed Machine Learning
               Nina Balcan, Carnegie Mellon University
               Slides   Video

               Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality
               Mark Braverman, Princeton University
               Slides   Video

               Sudipto Guha, University of Pennsylvania
   
               The Latest on Linear Sketching for Large Graphs: Lots of Problems, Little Space
               Andrew McGregor, University of Massachusetts, Amherst
               Slides   Video

               Parallel Peeling Algorithms 
               Justin Thaler, Yahoo! Research, NYC
               Slides   Video