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.

Image for "Data Science in Low-dimensional Spaces"
This workshop is part of the Brown Data Science Initiative project, funded by the National Science Foundation's TRIPODS program.

Confirmed Speakers & Participants

Talks will be presented virtually or in-person as indicated in the schedule below.

  • 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
Data Science in Low-dimensional Spaces
Play

Dimension Reduction for k-means via Random Projections

Chris Schwiegelshohn
Sapienza University of Rome
May 17, 2019
Data Science in Low-dimensional Spaces
Play

Pseudodimension for data analysis

Matteo Riondato
Amherst College
May 17, 2019
Data Science in Low-dimensional Spaces
Play     Slides

Partisan Segregation

Ryan Enos
Harvard University
May 16, 2019
Data Science in Low-dimensional Spaces
Play

Exploring Manifolds of Local Optima via Langevin Dynamics

Ankur Moitra
MIT
May 16, 2019
Data Science in Low-dimensional Spaces
Play

Approximation Algorithms for Capacitated Facility-Placement and Vehicle-Routing Problems in Transportation Networks

Amariah Becker
Brown University
May 16, 2019
Data Science in Low-dimensional Spaces
Play

Algorithms for Hard Problems on Low Highway Dimension Graphs

Andreas Feldmann
Charles University
May 16, 2019
Data Science in Low-dimensional Spaces
Play     Slides

On metric embeddings, shortest path decompositions and face cover of planar graphs

Arnold Filtser
Ben-Gurion University
May 15, 2019
Data Science in Low-dimensional Spaces
Play     Abstract     Slides

Distance oracles for planar graphs

Shay Mozes
Interdisciplinary Center Herzliya
May 15, 2019
Data Science in Low-dimensional Spaces
Play     Abstract     Slides

Planar Diameter via Metric Compression

Jason Li
Carnegie Mellon University
May 15, 2019
Data Science in Low-dimensional Spaces
Play

Graphs and Computational Geometry

Sergio Cabello
University of Ljubljana
May 15, 2019
Data Science in Low-dimensional Spaces
Play     Abstract

Flood Risk Analysis on Terrains

Pankaj Agarwal
Duke University
May 15, 2019
Data Science in Low-dimensional Spaces
Play

Truly Optimal Euclidean Spanners in Low Dimensional Spaces

Hung Le
University of Victoria
May 14, 2019
Data Science in Low-dimensional Spaces
Play

Covering Metric Spaces by Few Trees

Ofer Neiman
Ben-Gurion University
May 14, 2019
Data Science in Low-dimensional Spaces
Play     Abstract     Slides

Generalization Bounds for Distance-Based Learning with High-Dimensional Domains and Codomains

Cyrus Cousins
Brown University
May 14, 2019
Data Science in Low-dimensional Spaces
Play     Slides

Dimensionality Reduction - Theoretical Analysis of Practical Measures

Nova Fandina
Hebrew University of Jerusalem
May 14, 2019
Data Science in Low-dimensional Spaces
Play     Abstract     Slides

All geometries are wrong but some are useful: the art of simplification in GIS

Joshua Lieberman
Harvard University
May 14, 2019
Data Science in Low-dimensional Spaces
Play     Slides

Towards Algorithms for Districting Plans that Perfectly Balance Population and Nearly Minimize Dispersion

Philip Klein
Brown University
May 13, 2019
Data Science in Low-dimensional Spaces
Play

Better algorithms for the k-cut problem

Anupam Gupta
Carnegie Mellon University
May 13, 2019
Data Science in Low-dimensional Spaces
Play

MapReduce algorithms for diversity maximization in doubling spaces

Andrea Pietracaprina
Università di Padova
May 13, 2019
Data Science in Low-dimensional Spaces
Play     Slides

MapReduce algorithms for center-based clustering in doubing spaces

Geppino Pucci
Università di Padova
May 13, 2019
Data Science in Low-dimensional Spaces
Play     Slides

Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics

Vincent Cohen-Addad
CNRS & Sorbonne Université
May 13, 2019
Data Science in Low-dimensional Spaces
Play