Organizer(s):

Alexandr Andoni, Columbia University

Michal Koucký, Charles University

Barna Saha, University of California, San Diego

Mike Saks, Rutgers University

Description

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.

Program

Monday, May 6, 2024

Tuesday, May 7, 2024

Wednesday, May 8, 2024

Thursday, May 9, 2024

Call For Participation

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.

Code of Conduct

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.

Presented in association with the Special Focus on Lower Bounds in Computational Complexity.

Registration for this event is closed.