« search calendars

« DIMACS Workshop on Efficient Algorithms for High Dimensional Metrics: New Tools

DIMACS Workshop on Efficient Algorithms for High Dimensional Metrics: New Tools

May 06, 2024 - May 09, 2024

Location:

DIMACS Center

Rutgers University

CoRE Building

96 Frelinghuysen Road

Piscataway, NJ 08854

Click here for map.

Organizer(s):

Alexandr Andoni, Columbia University

Michal Koucký, Charles University

Barna Saha, University of California, San Diego

Mike Saks, Rutgers University

There are many open questions concerning algorithms related to distance measures that are not given by a norm, such as edit distance, Ulam distance, earth mover distance (Wasserstein metric), and Frechet distance. For each of these measures there are substantial gaps in our understanding of fundamental algorithmic problems such as computing, sketching, and nearest neighbor search.

The goal of this workshop is to explore and develop new tools relevant to these algorithmic problems. A prominent example of such a generic tool is metric embeddings, which map a complicated metric space into an algorithmically simpler space while preserving all distances within some small distortion factor. Such embeddings are a key tool for algorithmic applications and data structure design, e.g., for the nearest neighbor search.

For each of the aforementioned metrics there are longstanding open questions regarding the embeddings into simple spaces that minimize the worst case distortion. Recently researchers have considered relaxed notions of embeddings such as the average distortion embeddings and sketching that raise a host of new questions. Initial results on these questions have yielded significant algorithmic successes for some applications.

This workshop will bring together researchers working in computational aspects of distance measures including sketching, data structures, nearest neighbor search, string problems and communication complexity to stimulate further progress in the field. The workshop will consist of several tutorials on recent advances in the field and contributed talks. We plan for ample time for discussions in smaller groups.

Confirmed tutorial speakers:

  • Anne Driemel, University of Bonn
  • Tomasz Kociumaka, Max Planck Institute for Informatics
  • Aleksandar Nikolov, University of Toronto

View video playlist.

 

Monday, May 6, 2024

8:45 AM - 9:30 AM

Breakfast and Registration

9:30 AM - 9:45 AM

Welcome by organizers

9:45 AM - 10:45 AM
10:45 AM - 11:00 AM

Break (15 minutes)

11:00 AM - 12:00 PM
2:30 PM - 2:45 PM

Welcome by DIMACS

2:45 PM - 3:15 PM

Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations

Piotr Indyk, Massachusetts Institute of Technology

3:15 PM - 3:45 PM

Data-Dependent LSH for the Earth Mover's Distance

Erik Waingarten, University of Pennsylvania

3:45 PM - 4:15 PM

Probabilistic Embedding in MPC

MohammadTaghi Hajiaghayi, University of Maryland

4:15 PM - 4:30 PM

Break (15 minutes)

4:30 PM - 5:30 PM

Open Problems Session

 

Tuesday, May 7, 2024

8:45 AM - 9:30 AM

Breakfast and Registration

9:30 AM - 10:30 AM

Data Structures for Fréchet Queries

Anne Driemel, University of Bonn

10:30 AM - 11:00 AM

Break (30 minutes)

11:00 AM - 12:00 PM

Clustering Curves under the Fréchet Distance

Anne Driemel, University of Bonn

3:00 PM - 3:30 PM
3:30 PM - 4:00 PM
4:00 PM - 4:30 PM

Break (30 minutes)

4:30 PM - 5:00 PM

Consistent Clustering

Diptarka Chakraborty, National University of Singapore

 

Wednesday, May 8, 2024

8:45 AM - 9:30 AM

Breakfast and Registration

9:30 AM - 10:30 AM

Dynamic Algorithms for Edit Distance - Part I

Tomasz Kociumaka, Max Planck Institute for Informatics

10:30 AM - 11:00 AM

Break (30 minutes)

11:00 AM - 12:00 PM

Dynamic Algorithms for Edit Distance - Part II

Tomasz Kociumaka, Max Planck Institute for Informatics

3:00 PM - 3:30 PM

Embedding Edit Distance into Hamming Distance

Elazar Goldenberg, Academic College of Tel Aviv-Yaffo

3:30 PM - 4:00 PM
4:00 PM - 4:30 PM

Break (30 minutes)

4:30 PM - 5:00 PM
5:00 PM - 5:30 PM

Recovery from Non-Decomposable Distance Oracles

David P. Woodruff, Carnegie Mellon University

 

Thursday, May 9, 2024

8:45 AM - 9:30 AM

Breakfast and Registration

9:30 AM - 10:15 AM

On Sparse Partitions

Arnold Filtser, Bar-Ilan University

10:15 AM - 10:45 AM

Streaming Facility Location in High Dimension

Pavel Vesely, Charles University

10:45 AM - 11:15 AM

Fully Scalable MPC Algorithms for Clustering in High Dimension

Robert Krauthgamer, Weizmann Institute of Science

11:15 AM - 11:30 AM

Break (15 minutes)

11:30 AM - 12:00 PM

Light Spanners in High Dimension

Ofer Neiman, Ben Gurion University

12:00 PM - 12:30 PM

Faster Sublinear-Time Edit Distance

Nick Fischer, Weizmann Institute of Science

2:00 PM - 4:00 PM

Discussions

 

Presentations at this workshop are by invitation but others are welcome to attend. There is no fee to attend but registration is required. Please register using the button at the bottom of the page. Space is limited, so please register early if you plan to attend.

Update [March 18, 2024]: The workshop registration has been closed because we are at capacity. If you would like to join a waiting list, please send email to workshop@dimacs.rutgers.edu.

 

Request support: There are limited funds available to support travel by those whose attendance is contingent on support. We encourage diverse and inclusive participation and will prioritize applications for support from students and postdocs, especially those from minority or underrepresented groups. To apply for travel support please complete this form by March 15, 2024 and do not book your tickets until you hear from us! Since funds are limited, applying early provides the best access to funds.

Update [March 16, 2024]: The application for travel support is now closed.

 

Parking: If you do not have a Rutgers parking permit and you plan to drive to the workshop, there will be free parking in Lot 64, which is adjacent to the CoRE Building, but you must register your car to park. A link to register for parking will be provided in the confirmation message you receive when you register for the workshop.

 

Restaurants: For those staying in New Brunswick, there is a wide variety of restaurants within walking distance of the Heldrich and Hyatt hotels. Here are a few options.

The workshop is presented in cooperation with project CoSP, funded by European Union’s Horizon 2020 research and innovation programme under the Marie SkÅ‚odowska-Curie grant agreement No 823748.

Registration for this event is closed.