Bridging Theoretical Foundations and Industrial Frontiers. A workshop bringing together researchers and practitioners to discuss the latest advancements in ANNS.
Approximate Nearest Neighbor Search (ANNS) has a long history in theoretical computer science; ANNS has been used as a crucial tool in many areas such as approximation algorithms, optimization, streaming, and others, as well as being a central problem of study in its own right. Concurrently, the last decade has seen an explosion of ANNS usage in industry where it is known as retrieval or vector search. This explosion has been fueled by neural embedding models that represent complex data—such as text, images, and video—as high-dimensional vectors, making vector retrieval the heart of modern search applications.
Despite addressing the same fundamental problem, the theoretical and applied communities have developed largely independently. Extremely popular algorithms used in practice, such as HNSW, FAISS, ScaNN, and DiskANN, have evolved with distinct techniques and terminology, creating a disconnect between theoretical foundations and industrial frontiers. While recent efforts have begun to analyze these applied algorithms through a theoretical lens, there remains a significant gap between the languages and frameworks used by these two communities.
The goal of this workshop is to bridge this divide by surveying techniques from both worlds and examining the current state of modern vector retrieval. We aim to treat practical deployments not merely as applications, but as a source of deep, challenging theoretical questions that invite a reevaluation of how TCS views the ANNS problem. By disseminating ideas between these disciplines, the workshop will facilitate the development of new theoretical frameworks beyond standard worst-case guarantees and identify the most critical open problems in the field.
University of Tokyo
UPenn
Columbia University
Nanyang Technological University
EPFL
UPenn
Weizmann Institute
Sunday, December 14, 2025
Opening Remarks
Survey 1: Theoretical Foundations
Erik Waingarten (UPenn)
Coffee Break
Research Talk 1
Sanjeev Khanna (UPenn)
TBD
Research Talk 2
Robert Krauthgamer (Weizmann Institute)
TBD
Research Talk 3
Josh Alman (Columbia University)
TBD
Lunch (Provided)
Survey 2: Applied Algorithms & Systems
Yusuke Matsui (University of Tokyo)
TBD
Research Talk 4
Jianyang Gao (Nanyang Technological University)
TBD
Coffee Break
Research Talk 5
Michael Kapralov (EPFL)
TBD
Open Problems Session
Closing Remarks
