DIMACS Workshop on Efficient Algorithms for High Dimensional Metrics: New Tools
May 6 - 9, 2024
DIMACS Center, Busch Campus, Rutgers University
Organizers:
Alexandr Andoni, Columbia University
Michal Koucký, Charles University
Barna Saha, University of California, San Diego
Mike Saks, Rutgers University
Presented under the auspices of the DIMACS Special Focus on Lower Bounds in Computational Complexity<http://dimacs.rutgers.edu/programs/sf/sf-lowerbounds>.
*********************************************************************
Workshop Announcement:
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
*********************************************************************
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. If you would like to attend this workshop, please register at the workshop web page<http://dimacs.rutgers.edu/events/details?eID=2733> using the button at the bottom of the page. Space is limited, so please register early if you plan to attend.
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 and submit the form linked to the workshop webpage by March 15, 2024.
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.
*********************************************************************
Workshop web site (including registration):
http://dimacs.rutgers.edu/events/details?eID=2733
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
