Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
Fast Distance Oracles for Any Symmetric Norm
Authors: Yichuan Deng, Zhao Song, OMRI WEINSTEIN, Ruizhe Zhang
NeurIPS 2022 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contribution is a fast (1 ε) distance oracle for any symmetric norm l. We propose a novel data structure with e O(n(d + mmc(l)2)) preprocessing time and space, and tq = e O(d + |S| mmc(l)2) query time... Our work strengthens and unifies a long line of work on metric embeddings and sketching, by presenting the first Distance Oracle for any symmetric norm, with nearly-optimal query and update times. |
| Researcher Affiliation | Collaboration | Yichuan Deng University of Science and Technology of China EMAIL Zhao Song Adobe Research EMAIL Omri Weinstein The Hebrew University and Columbia University EMAIL Ruizhe Zhang The University of Texas at Austin EMAIL |
| Pseudocode | Yes | Algorithm 1 Data structure for symmetric norm estimation: members, init, informal version of Algorithm 4 and Algorithm 5. Algorithm 2 Data structure for symmetric norm estimation: query, informal version of Algorithm 7. |
| Open Source Code | No | The paper is theoretical and does not report experimental results. The author checklist explicitly states '[N/A]' for questions regarding code availability and reproduction of experimental results, indicating no open-source code for the methodology is provided. |
| Open Datasets | No | The paper is theoretical and does not include experimental results on datasets. The author checklist explicitly states '[N/A]' for questions related to experiments and data, indicating no public datasets were used in the context of empirical validation. |
| Dataset Splits | No | The paper is theoretical and does not report experimental results. Therefore, it does not specify training, validation, or test dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not report experimental results. The author checklist explicitly states '[N/A]' for questions related to experiments, indicating no hardware specifications were provided. |
| Software Dependencies | No | The paper is theoretical and does not report experimental results. The author checklist explicitly states '[N/A]' for questions related to experiments, indicating no software dependencies with version numbers were provided. |
| Experiment Setup | No | The paper is theoretical and does not report experimental results. The author checklist explicitly states '[N/A]' for questions related to experiments, indicating no experimental setup details were provided. |