Organizing Committee
Abstract

Data science in low-dimensional spaces is motivated by applications in mapping, navigation, geographic resource allocation, modeling of body shapes and chemical structures, and more. In addition to datasets that naturally reside in low-dimension spaces, dimension-reduction methods can often transform high dimensional data to lower-dimensional data while preserving properties of interest. Since many computational problems are intractable for high-dimensional data but potentially tractable for low-dimensional data, it is useful to establish the algorithmic foundations of data science on low-dimensional data, to understand the special properties of such data, and to identify computational methods that are highly effective when applied to such data.

This workshop will bring together researchers in academia and industry to explore algorithmic and data analysis technique specialized for low-dimensional data, and application areas in which such problems arise. The focus of this workshop is on algorithms with provable performance guarantees. In particular, we are interested in algorithms that scale to large datasets, and algorithms that adapts to distributed environments and to online settings.

Confirmed Speakers & Participants

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee

Workshop Schedule

Monday, May 13, 2019
TimeEventLocationMaterials
8:30 - 8:55am EDTRegistration - ICERM 121 South Main Street, Providence RI 0290311th Floor Collaborative Space 
8:55 - 9:00am EDTWelcome - ICERM Director11th Floor Lecture Hall 
9:00 - 9:45am EDTNear-Linear Time Approximation Schemes for Clustering in Doubling Metrics - Vincent Cohen-Addad, CNRS & Sorbonne Université11th Floor Lecture Hall 
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTMapReduce algorithms for center-based clustering in doubing spaces - Geppino Pucci, Università di Padova11th Floor Lecture Hall
11:30 - 12:15pm EDTMapReduce algorithms for diversity maximization in doubling spaces - Andrea Pietracaprina, Università di Padova11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch / Free Time  
2:30 - 3:15pm EDTA Global Notion of Metric Dimension - Anupam Gupta, Carnegie Mellon University11th Floor Lecture Hall 
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTTowards Algorithms for Districting Plans that Perfectly Balance Population and Nearly Minimize Dispersion - Philip Klein, Brown University11th Floor Lecture Hall 
5:00 - 6:30pm EDTWelcome Reception11th Floor Collaborative Space 
Tuesday, May 14, 2019
TimeEventLocationMaterials
9:00 - 9:45am EDTAll geometries are wrong but some are useful - the art of simplification in GIS - Joshua Lieberman, Harvard University11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTDimensionality Reduction - Theoretical Analysis of Practical Measures - Nova Fandina, Hebrew University of Jerusalem11th Floor Lecture Hall
11:30 - 12:15pm EDTGeneralization Bounds for Distance-Based Learning with High-Dimensional Domains and Codomains - Cyrus Cousins, Brown University11th Floor Lecture Hall
12:30 - 2:30pm EDTBreak for Lunch / Free Time  
2:30 - 3:15pm EDTCovering Metric Spaces by Few Trees - Ofer Neiman, Ben-Gurion University11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTTruly Optimal Euclidean Spanners in Low Dimensional Spaces - Hung Le, University of Victoria11th Floor Lecture Hall 
Wednesday, May 15, 2019
TimeEventLocationMaterials
9:00 - 9:45am EDTFlood Risk Analysis on Terrains - Pankaj Agarwal, Duke University11th Floor Lecture Hall 
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTGraphs and Computational Geometry - Sergio Cabello, University of Ljubljana11th Floor Lecture Hall
11:30 - 12:15pm EDTPlanar Diameter via Metric Compression - Jason Li, Carnegie Mellon University11th Floor Lecture Hall 
12:30 - 1:00pm EDTGroup Photo11th Floor Lecture Hall 
12:40 - 2:30pm EDTBreak for Lunch / Free Time  
2:30 - 3:15pm EDTDistance oracles for planar graphs - Shay Mozes, Interdisciplinary Center Herzliya11th Floor Lecture Hall
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTOn metric embeddings, shortest path decompositions and face cover of planar graphs - Arnold Filtser, Ben-Gurion University11th Floor Lecture Hall
Thursday, May 16, 2019
TimeEventLocationMaterials
9:00 - 9:45am EDTAlgorithms for Hard Problems on Low Highway Dimension Graphs - Andreas Feldmann, Charles University11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTScalable Algorithms for Last-Mile Delivery - Renato Werneck, Amazon11th Floor Lecture Hall 
11:30 - 12:15pm EDTApproximation Algorithms for Capacitated Vehicle Routing Problems in Transportation Networks - Amariah Becker, Brown University11th Floor Lecture Hall 
12:30 - 2:30pm EDTBreak for Lunch / Free Time  
2:30 - 3:15pm EDTLearning GGMs without Condition Number Bounds - Ankur Moitra, MIT11th Floor Lecture Hall 
3:30 - 4:00pm EDTCoffee/Tea Break11th Floor Collaborative Space 
4:00 - 4:45pm EDTPartisan Segregation - Ryan Enos, Harvard University11th Floor Lecture Hall 
Friday, May 17, 2019
TimeEventLocationMaterials
9:00 - 9:45am EDTPseudodimension for data analysis - Matteo Riondato, Amherst College11th Floor Lecture Hall
10:00 - 10:30am EDTCoffee/Tea Break11th Floor Collaborative Space 
10:30 - 11:15am EDTDimension Reduction for k-means via Random Projections - Chris Schwiegelshohn, Sapienza University of Rome11th Floor Lecture Hall 
11:30 - 12:15pm EDTAlgorithms for metric learning via contrastive embeddings. - Anastasios (Tasos) Sidiropoulos, University of Illinois at Chicago11th Floor Lecture Hall 

Lecture Videos

Algorithms for metric learning via contrastive embeddings

Anastasios (Tasos) Sidiropoulos
University of Illinois at Chicago
May 17, 2019

Dimension Reduction for k-means via Random Projections

Chris Schwiegelshohn
Sapienza University of Rome
May 17, 2019

Partisan Segregation

Ryan Enos
Harvard University
May 16, 2019

Distance oracles for planar graphs

Shay Mozes
Interdisciplinary Center Herzliya
May 15, 2019

Graphs and Computational Geometry

Sergio Cabello
University of Ljubljana
May 15, 2019

Better algorithms for the k-cut problem

Anupam Gupta
Carnegie Mellon University
May 13, 2019