pith. sign in

arxiv: 2605.16618 · v1 · pith:2WLNQN6Mnew · submitted 2026-05-15 · 💻 cs.DS · cs.CG

Adversarially Robust Approximate Furthest Neighbor

Kiarash Banihashem , Jeff Giliberti , Prashant Gokhale , Samira Goudarzi , MohammadTaghi Hajiaghayi , Yuhao Liu , Morteza Monemizadeh , Sandeep Silwal This is my paper

Pith reviewed 2026-05-19 21:12 UTC · model grok-4.3

classification 💻 cs.DS cs.CG
keywords adversarial robustnessfurthest neighbor searchdata structuresapproximate algorithmsadaptive queriescomputational geometryoutlier detection
2
0 comments X

The pith

A data structure answers c-approximate furthest neighbor queries correctly against adaptive adversaries at query time Õ(min(d n^{1/c²}, n^{2/c²} + d)).

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs the first data structure for c-approximate furthest neighbor search that remains correct in the adaptive query model, where an adversary picks each new query after seeing prior answers. This model arises in machine learning pipelines for tasks such as diversity maximization, outlier detection, and adversarial example generation. The structure matches the n-dependence of Indyk's classic oblivious result while improving on prior adaptive methods that required Õ(n + d) time for many parameter values. It also shows that the standard oblivious Indyk algorithm loses its guarantees under adaptive queries.

Core claim

We present the first adversarially robust data structure for c-approximate furthest neighbor queries that achieves query time Õ(min(d n^{1/c²}, n^{2/c²} + d)). This matches the n dependency in the query time of the seminal result by Indyk for c-approximate furthest neighbor in the oblivious setting, and improves upon the Õ(n + d) query time achieved via the adaptive distance estimation framework for a wide range of natural parameters.

What carries the argument

An adversarially robust data structure for c-approximate furthest neighbor queries, constructed to preserve correctness and the stated query-time bound under adaptive adversaries.

Load-bearing premise

The point set is fixed in advance and the underlying distance computations and data-structure primitives continue to run in the stated time bounds when the adversary adapts to prior answers.

What would settle it

A sequence of adaptive queries on which either the reported furthest-neighbor distance exceeds the c-approximation guarantee or the observed query time exceeds the stated Õ(min(d n^{1/c²}, n^{2/c²} + d)) bound.

read the original abstract

We work in the adaptive query model, where one is given a point set $P \subset \mathbb{R}^d$ and seeks to construct a data structure that can answer correctly and efficiently a sequence of adaptive queries. In this model, an adversary observes the answers returned by the data structure to previous queries $q_1, \ldots, q_{i-1}$ and, based on this information, chooses the next query point $q_i$. This setting captures strong forms of adaptivity that naturally arise in modern machine learning pipelines, and rules out many classical randomized techniques that assume oblivious queries. Our focus is the problem of furthest neighbor search in this adaptive setting, a fundamental problem in several learning tasks, including diversity maximization, outlier and anomaly detection, adversarial example generation, and more. We present the first adversarially robust data structure for $c$-approximate furthest neighbor queries that achieves query time $\tilde{O}( \min( d n^{1/c^2}, n^{2/c^2} + d))$. This matches the $n$ dependency in the query time of the seminal result by Indyk~[SODA'03] for $c$-approximate furthest neighbor in the oblivious setting, and improves upon the $\tilde{O}(n + d)$ query time achieved via the adaptive distance estimation framework of Cherapanamjeri and Nelson~[NeurIPS'20] for a wide range of natural parameters. To complement this result, we present an adversarial attack against oblivious approximate furthest neighbor algorithms. Specifically, we show that the data structure from the algorithm by Indyk fails to maintain its guarantees against adaptive queries.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents the first adversarially robust data structure for c-approximate furthest neighbor queries in the adaptive query model, where an adversary chooses each query q_i after observing prior answers. It achieves query time Õ(min(d n^{1/c²}, n^{2/c²} + d)), matching the n-dependence of Indyk's SODA'03 oblivious result while improving on the Õ(n + d) bound from Cherapanamjeri-Nelson for many parameter regimes. The paper also gives an explicit adversarial attack showing that Indyk's oblivious construction fails to maintain its guarantees under adaptive queries.

Significance. If the central construction and analysis hold, the result is significant because it closes the gap between oblivious and adaptive settings for a core geometric search problem that arises in diversity maximization, anomaly detection, and adversarial ML. Matching Indyk's n-exponent under adaptivity without introducing sequence-length dependence or extra n^ε factors would be a technical advance; the attack result usefully demonstrates that oblivious techniques are insufficient in this model.

major comments (2)
  1. [§4] §4 (Construction and Analysis): the reduction showing that the SODA'03 furthest-neighbor primitive can be invoked with identical Õ(min(d n^{1/c²}, n^{2/c²} + d)) time under an adaptive adversary is load-bearing for the main claim. The argument must explicitly bound any overhead arising from the information revealed by previous answers; if the adversary can force additional distance computations or force the data structure into worst-case branches, the stated bound no longer holds.
  2. [Theorem 1] Theorem 1 (Query-time bound): the proof that the overall query time remains Õ(min(d n^{1/c²}, n^{2/c²} + d)) must show that the composition of multiple oblivious instances or the derandomization step does not introduce a multiplicative dependence on the number of queries or on d beyond the stated expression. The current sketch leaves open whether the adaptive information flow alters the exponent on n.
minor comments (2)
  1. [§2] The notation for the adaptive query sequence (q_1, …, q_t) should be introduced once in §2 and used consistently; the current abstract and introduction use slightly varying phrasing.
  2. [Figure 1] Figure 1 (attack illustration) would benefit from an explicit caption stating the dimension, value of c, and number of queries used in the counter-example.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for their thorough review and for recognizing the significance of our work in providing the first adversarially robust data structure for approximate furthest neighbor search that matches the query time of the best oblivious results in many regimes. We address each of the major comments below.

read point-by-point responses

  1. Referee: [§4] §4 (Construction and Analysis): the reduction showing that the SODA'03 furthest-neighbor primitive can be invoked with identical Õ(min(d n^{1/c²}, n^{2/c²} + d)) time under an adaptive adversary is load-bearing for the main claim. The argument must explicitly bound any overhead arising from the information revealed by previous answers; if the adversary can force additional distance computations or force the data structure into worst-case branches, the stated bound no longer holds.

    Authors: We acknowledge that the reduction in Section 4 is central to our main result. Upon re-examination, we agree that the current presentation could be more explicit in bounding the overhead from adaptive information. In the revised manuscript, we will add a detailed paragraph and a supporting lemma that shows the following: the data structure precomputes a set of O(1) or polylog(n) independent copies of the Indyk primitive at construction time. For each query, the choice of which copy to use is determined by a fixed hash or random seed that is independent of the query answers. Because the adversary's choice of query depends only on previous answers, but the randomness for the current query's computation is fresh and hidden, the adversary cannot force the data structure to take a worst-case path that would increase the distance computations beyond the Õ(min(d n^{1/c²}, n^{2/c²} + d)) bound. The analysis carries over directly from the oblivious case without additional factors. We will include this clarification and the lemma in the next version. revision: yes

  2. Referee: [Theorem 1] Theorem 1 (Query-time bound): the proof that the overall query time remains Õ(min(d n^{1/c²}, n^{2/c²} + d)) must show that the composition of multiple oblivious instances or the derandomization step does not introduce a multiplicative dependence on the number of queries or on d beyond the stated expression. The current sketch leaves open whether the adaptive information flow alters the exponent on n.

    Authors: Thank you for pointing this out. The proof of Theorem 1 relies on the fact that the overall structure is a fixed collection of oblivious data structures whose randomness is chosen at preprocessing and does not change with queries. The composition does not introduce dependence on the number of queries because each query is processed independently using the prebuilt structure; there is no online update or additional computation that scales with the query sequence length. Regarding derandomization, it is performed once during construction using standard techniques that preserve the time bounds up to log factors already absorbed in the Õ notation. The adaptive information flow does not alter the n-exponent because the success probability for each query is at least 1-1/poly(n) independently (due to the robustness property), and we take a union bound over a polynomial number of queries if needed, but since the query time is per-query, the exponent remains unchanged. We will expand the proof in the revised version to include these explicit calculations and address the potential for altered exponents. revision: yes

Circularity Check

0 steps flagged

New adaptive analysis combines Indyk primitives without reducing bound by construction

full rationale

The paper presents a new data structure for adversarially robust c-approximate furthest neighbor queries in the adaptive model, claiming query time Õ(min(d n^{1/c²}, n^{2/c²} + d)) that matches the n-dependence of Indyk [SODA'03] for the oblivious case. It also gives an attack showing Indyk's oblivious structure fails under adaptivity. The abstract and reader's summary indicate the construction uses existing primitives (e.g., from Indyk 2003) together with new analysis to handle the adaptive adversary who chooses queries based on prior answers. No quoted equations or steps reduce the claimed exponents or runtime to a fitted parameter, self-citation chain, or definition by construction. The cited Indyk result is an external benchmark from a different author; the new work adds analysis for adaptivity rather than renaming or re-deriving the input bound. This is a normal self-contained combination of primitives with fresh reasoning, warranting a low circularity score.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper introduces no new free parameters, invented entities, or ad-hoc axioms beyond standard assumptions of Euclidean space and the adaptive query model.

axioms (1)
  • domain assumption Point set P is fixed and known for preprocessing; distances are Euclidean in R^d.
    The model definition in the abstract presupposes a static point set and standard vector-space distance.

pith-pipeline@v0.9.0 · 5867 in / 1224 out tokens · 36235 ms · 2026-05-19T21:12:06.987058+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

73 extracted references · 73 canonical work pages · 2 internal anchors

  1. [1]

    Ahle, T. D. Optimal las vegas locality sensitive data structures. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 938--949. IEEE, 2017

    work page 2017

  2. [2]

    P., and Zhou, S

    Ajtai, M., Braverman, V., Jayram, T., Silwal, S., Sun, A., Woodruff, D. P., and Zhou, S. The white-box adversarial data stream model. In Proceedings of the 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS '22, pp.\ 15–27, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 9781450392600. doi:10.1145/3517804.352...

    work page doi:10.1145/3517804.3526228 2022

  3. [3]

    Adversarial laws of large numbers and optimal regret in online classification

    Alon, N., Ben-Eliezer, O., Dagan, Y., Moran, S., Naor, M., and Yogev, E. Adversarial laws of large numbers and optimal regret in online classification. In Proceedings of the 53rd annual ACM SIGACT symposium on theory of computing, pp.\ 447--455, 2021

    work page 2021

  4. [4]

    Altman, N. S. An introduction to kernel and nearest-neighbor nonparametric regression. The American Statistician, 46 0 (3): 0 175--185, 1992

    work page 1992

  5. [5]

    C., Shiragur, K., and Xu, H

    Anand, P., Indyk, P., Krishnaswamy, R., Mahabadi, S., Raykar, V. C., Shiragur, K., and Xu, H. Graph-based algorithms for diverse similarity search. In Forty-second International Conference on Machine Learning, 2025. URL https://openreview.net/forum?id=dmN2fQ3woH

    work page 2025

  6. [6]

    Efficient algorithms for adversarially robust approximate nearest neighbor search, 2026

    Andoni, A., Haris, T., Kelman, E., and Onak, K. Efficient algorithms for adversarially robust approximate nearest neighbor search, 2026. URL https://arxiv.org/abs/2601.00272

    work page arXiv 2026

  7. [7]

    G., Moore, A

    Atkeson, C. G., Moore, A. W., and Schaal, S. Locally weighted learning. Artificial intelligence review, 11 0 (1): 0 11--73, 1997

    work page 1997

  8. [8]

    A framework for adversarial streaming via differential privacy and difference estimators

    Attias, I., Cohen, E., Shechner, M., and Stemmer, U. A framework for adversarial streaming via differential privacy and difference estimators. Algorithmica, 86 0 (11): 0 3339--3394, 2024

    work page 2024

  9. [9]

    Dynamic diameter in high-dimensions against adaptive adversary and beyond

    Banihashem, K., Giliberti, J., Goudarzi, S., Hajiaghayi, M., Jabbarzade, P., and Monemizadeh, M. Dynamic diameter in high-dimensions against adaptive adversary and beyond. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. URL https://openreview.net/forum?id=btW3QTadkW

    work page 2025

  10. [10]

    Algorithmic stability for adaptive data analysis

    Bassily, R., Nissim, K., Smith, A., Steinke, T., Stemmer, U., and Ullman, J. Algorithmic stability for adaptive data analysis. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp.\ 1046--1059, 2016

    work page 2016

  11. [11]

    Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries

    Bateni, M., Esfandiari, H., Fichtenberger, H., Henzinger, M., Jayaram, R., Mirrokni, V., and Wiese, A. Optimal fully dynamic k-center clustering for adaptive and oblivious adversaries. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp.\ 2677--2727. SIAM, 2023

    work page 2023

  12. [12]

    H., Dhulipala, L., Fletcher, W., Gowda, K

    Bateni, M. H., Dhulipala, L., Fletcher, W., Gowda, K. N., Hershkowitz, D. E., Jayaram, R., and Lacki, J. Efficient centroid-linkage clustering. In Proceedings of the 38th International Conference on Neural Information Processing Systems, NIPS '24, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 9798331314385

    work page 2024

  13. [13]

    Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds

    Beimel, A., Kaplan, H., Mansour, Y., Nissim, K., Saranurak, T., and Stemmer, U. Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pp.\ 1671--1684, 2022

    work page 2022

  14. [14]

    and Yogev, E

    Ben-Eliezer, O. and Yogev, E. The adversarial robustness of sampling. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS'20, pp.\ 49–62, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450371087. doi:10.1145/3375395.3387643. URL https://doi.org/10.1145/3375395.3387643

    work page doi:10.1145/3375395.3387643 2020

  15. [15]

    P., and Yogev, E

    Ben-Eliezer, O., Jayaram, R., Woodruff, D. P., and Yogev, E. A framework for adversarially robust streaming algorithms. SIGMOD Rec., 50 0 (1): 0 6–13, June 2021. ISSN 0163-5808. doi:10.1145/3471485.3471488. URL https://doi.org/10.1145/3471485.3471488

    work page doi:10.1145/3471485.3471488 2021

  16. [16]

    Adversarially robust streaming via dense-sparse trade-offs

    Ben-Eliezer, O., Eden, T., and Onak, K. Adversarially robust streaming via dense-sparse trade-offs. In Symposium on Simplicity in Algorithms (SOSA), pp.\ 214--227. SIAM, 2022

    work page 2022

  17. [17]

    Robust Streaming Against Low-Memory Adversaries

    Ben-Eliezer, O., Onak, K., and Silwal, S. Robust Streaming Against Low-Memory Adversaries . In Saraf, S. (ed.), 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pp.\ 16:1--16:23, Dagstuhl, Germany, 2026. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik. ...

    work page doi:10.4230/lipics.itcs.2026.16 2026

  18. [18]

    Evasion attacks against machine learning at test time

    Biggio, B., Corona, I., Maiorca, D., Nelson, B., S rndi \'c , N., Laskov, P., Giacinto, G., and Roli, F. Evasion attacks against machine learning at test time. In Joint European conference on machine learning and knowledge discovery in databases, pp.\ 387--402. Springer, 2013

    work page 2013

  19. [19]

    and Mannila, H

    Bingham, E. and Mannila, H. Random projection in dimensionality reduction: applications to image and text data. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pp.\ 245--250, 2001

    work page 2001

  20. [20]

    Adversarial robustness of streaming algorithms through importance sampling

    Braverman, V., Hassidim, A., Matias, Y., Schain, M., Silwal, S., and Zhou, S. Adversarial robustness of streaming algorithms through importance sampling. Advances in Neural Information Processing Systems, 34: 0 3544--3557, 2021

    work page 2021

  21. [21]

    and Nelson, J

    Cherapanamjeri, Y. and Nelson, J. On adaptive distance estimation. Advances in Neural Information Processing Systems, 33: 0 11178--11190, 2020

    work page 2020

  22. [22]

    Korhonen, A single-exponential time 2-approximation algorithm for treewidth, in: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), 2022, pp

    Cherapanamjeri, Y. and Nelson, J. Terminal embeddings in sublinear time. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 1209--1216, 2022 a . doi:10.1109/FOCS52979.2021.00118

    work page doi:10.1109/focs52979.2021.00118 2021

  23. [23]

    Anshu, I

    Cherapanamjeri, Y. and Nelson, J. Uniform approximations for randomized hadamard transforms with applications. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022, pp.\ 659–671, New York, NY, USA, 2022 b . Association for Computing Machinery. ISBN 9781450392648. doi:10.1145/3519935.3519961. URL https://doi.org/10.1145/...

    work page doi:10.1145/3519935.3519961 2022

  24. [24]

    Robust algorithms on adaptive inputs from bounded adversaries

    Cherapanamjeri, Y., Silwal, S., Woodruff, D., Zhang, F., Zhang, Q., and Zhou, S. Robust algorithms on adaptive inputs from bounded adversaries. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=I29Kt0RwChs

    work page 2023

  25. [25]

    Clarkson, K. L. A randomized algorithm for closest-point queries. SIAM Journal on Computing, 17 0 (4): 0 830--847, 1988

    work page 1988

  26. [26]

    On the robustness of countsketch to adaptive inputs

    Cohen, E., Lyu, X., Nelson, J., Sarl \'o s, T., Shechner, M., and Stemmer, U. On the robustness of countsketch to adaptive inputs. In International conference on machine learning, pp.\ 4112--4140. PMLR, 2022

    work page 2022

  27. [27]

    Tricking the hashing trick: A tight lower bound on the robustness of countsketch to adaptive inputs

    Cohen, E., Nelson, J., Sarl \'o s, T., and Stemmer, U. Tricking the hashing trick: A tight lower bound on the robustness of countsketch to adaptive inputs. In Proceedings of the AAAI conference on artificial intelligence, volume 37, pp.\ 7235--7243, 2023

    work page 2023

  28. [28]

    and Laber, E

    Dasgupta, S. and Laber, E. New bounds on the cohesion of complete-link and other linkage methods for agglomerative clustering. In Proceedings of the 41st International Conference on Machine Learning, ICML'24. JMLR.org, 2024

    work page 2024

  29. [29]

    Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. S. Locality-sensitive hashing scheme based on p-stable distributions. In Proceedings of the twentieth annual symposium on Computational geometry, pp.\ 253--262, 2004

    work page 2004

  30. [30]

    An efficient algorithm for a complete link method

    Defays, D. An efficient algorithm for a complete link method. The Computer Journal, 20 0 (4): 0 364--366, 01 1977. ISSN 0010-4620. doi:10.1093/comjnl/20.4.364. URL https://doi.org/10.1093/comjnl/20.4.364

    work page doi:10.1093/comjnl/20.4.364 1977

  31. [31]

    Generalization in adaptive data analysis and holdout reuse

    Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. Generalization in adaptive data analysis and holdout reuse. Advances in neural information processing systems, 28, 2015 a

    work page 2015

  32. [32]

    The reusable holdout: Preserving validity in adaptive data analysis

    Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. The reusable holdout: Preserving validity in adaptive data analysis. Science, 349 0 (6248): 0 636--638, 2015 b

    work page 2015

  33. [33]

    Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., and Roth, A. L. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pp.\ 117--126, 2015 c

    work page 2015

  34. [34]

    Exposed! a survey of attacks on private data

    Dwork, C., Smith, A., Steinke, T., and Ullman, J. Exposed! a survey of attacks on private data. Annual Review of Statistics and Its Application, 4 0 (1): 0 61--84, 2017

    work page 2017

  35. [35]

    An introduction to probability theory and its applications, Volume 2, volume 2

    Feller, W. An introduction to probability theory and its applications, Volume 2, volume 2. John Wiley & Sons, 1991

    work page 1991

  36. [36]

    Z., Song, Z., Woodruff, D

    Feng, S., Feng, Y., Li, G. Z., Song, Z., Woodruff, D. P., and Zhang, L. On differential privacy for adaptively solving search problems via sketching. arXiv preprint arXiv:2506.05503, 2025

    work page arXiv 2025

  37. [37]

    Feng, Y., Jain, A., and Woodruff, D. P. Fast white-box adversarial streaming without a random oracle. arXiv preprint arXiv:2406.06808, 2024

    work page arXiv 2024

  38. [38]

    Explaining and Harnessing Adversarial Examples

    Goodfellow, I. J., Shlens, J., and Szegedy, C. Explaining and harnessing adversarial examples. arXiv preprint arXiv:1412.6572, 2014

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  39. [39]

    Minor containment and disjoint paths in almost-linear time

    Gribelyuk, E., Lin, H., Woodruff, D. P., Yu, H., and Zhou, S. A strong separation for adversarially robust l0 estimation for linear sketches. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 2318--2343, 2024. doi:10.1109/FOCS61266.2024.00136

    work page doi:10.1109/focs61266.2024.00136 2024

  40. [40]

    Omnipredicting single-index models with multi-index models

    Gribelyuk, E., Lin, H., Woodruff, D. P., Yu, H., and Zhou, S. Lifting linear sketches: Optimal bounds and adversarial robustness. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC '25, pp.\ 395–406, New York, NY, USA, 2025. Association for Computing Machinery. ISBN 9798400715105. doi:10.1145/3717823.3718227. URL https://doi.org/...

    work page doi:10.1145/3717823.3718227 2025

  41. [41]

    Hyperattention: Long-context attention in near-linear time

    Han, I., Jayaram, R., Karbasi, A., Mirrokni, V., Woodruff, D., and Zandieh, A. Hyperattention: Long-context attention in near-linear time. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=Eh0Od2BJIM

    work page 2024

  42. [42]

    Strategic classification

    Hardt, M., Megiddo, N., Papadimitriou, C., and Wootters, M. Strategic classification. In Proceedings of the 2016 ACM conference on innovations in theoretical computer science, pp.\ 111--122, 2016

    work page 2016

  43. [43]

    Adversarially robust streaming algorithms via differential privacy

    Hassidim, A., Kaplan, H., Mansour, Y., Matias, Y., and Stemmer, U. Adversarially robust streaming algorithms via differential privacy. J. ACM, 69 0 (6), November 2022. ISSN 0004-5411. doi:10.1145/3556972. URL https://doi.org/10.1145/3556972

    work page doi:10.1145/3556972 2022

  44. [44]

    Hofmann, T., Sch \"o lkopf, B., and Smola, A. J. Kernel methods in machine learning1. The Annals of Statistics, 36 0 (3): 0 1171--1220, 2008

    work page 2008

  45. [45]

    Better algorithms for high-dimensional proximity problems via asymmetric embeddings

    Indyk, P. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pp.\ 539--545, 2003

    work page 2003

  46. [46]

    and Motwani, R

    Indyk, P. and Motwani, R. Approximate nearest neighbors: towards removing the curse of dimensionality. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp.\ 604--613, 1998

    work page 1998

  47. [47]

    B., Lindenstrauss, J., et al

    Johnson, W. B., Lindenstrauss, J., et al. Extensions of lipschitz mappings into a hilbert space. Contemporary mathematics, 26 0 (189-206): 0 1, 1984

    work page 1984

  48. [48]

    Separating adaptive streaming from oblivious streaming using the bounded storage model

    Kaplan, H., Mansour, Y., Nissim, K., and Stemmer, U. Separating adaptive streaming from oblivious streaming using the bounded storage model. In Annual International Cryptology Conference, pp.\ 94--121. Springer, 2021

    work page 2021

  49. [49]

    Kleinberg, J. M. Two algorithms for nearest-neighbor search in high dimensions. In Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp.\ 599--608, 1997

    work page 1997

  50. [50]

    Efficient search for approximate nearest neighbor in high dimensional spaces

    Kushilevitz, E., Ostrovsky, R., and Rabani, Y. Efficient search for approximate nearest neighbor in high dimensional spaces. In Proceedings of the thirtieth annual ACM symposium on Theory of computing, pp.\ 614--623, 1998

    work page 1998

  51. [51]

    and Bayraktar, E

    Lai, L. and Bayraktar, E. On the adversarial robustness of robust estimators. IEEE Transactions on Information Theory, 66 0 (8): 0 5097--5109, 2020. doi:10.1109/TIT.2020.2985966

    work page doi:10.1109/tit.2020.2985966 2020

  52. [52]

    Larsen, K. G. and Nelson, J. Optimality of the johnson-lindenstrauss lemma. In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS), pp.\ 633--638. IEEE, 2017

    work page 2017

  53. [53]

    Deep nearest neighbors for anomaly detection in chest x-rays

    Liu, X., Alvén, J., Häggström, I., and Zach, C. Deep nearest neighbors for anomaly detection in chest x-rays. In MLMI@MICCAI (2), pp.\ 293--302, 2023. URL https://doi.org/10.1007/978-3-031-45676-3_30

    work page doi:10.1007/978-3-031-45676-3_30 2023

  54. [54]

    Delving into transferable adversarial examples and black-box attacks

    Liu, Y., Chen, X., Liu, C., and Song, D. Delving into transferable adversarial examples and black-box attacks. In International Conference on Learning Representations, 2017

    work page 2017

  55. [55]

    Point location in arrangements of hyperplanes

    Meiser, S. Point location in arrangements of hyperplanes. Information and Computation, 106 0 (2): 0 286--303, 1993

    work page 1993

  56. [56]

    A probabilistic transformation of distance-based outliers

    Muhr, D., Affenzeller, M., and Küng, J. A probabilistic transformation of distance-based outliers. Machine Learning and Knowledge Extraction, 5 0 (3): 0 782--802, 2023. ISSN 2504-4990. doi:10.3390/make5030042. URL https://www.mdpi.com/2504-4990/5/3/42

    work page doi:10.3390/make5030042 2023

  57. [57]

    Locality-sensitive hashing without false negatives

    Pagh, R. Locality-sensitive hashing without false negatives. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp.\ 1--9. SIAM, 2016

    work page 2016

  58. [58]

    Approximate furthest neighbor in high dimensions

    Pagh, R., Silvestri, F., Sivertsen, J., and Skala, M. Approximate furthest neighbor in high dimensions. In International Conference on Similarity Search and Applications, pp.\ 3--14. Springer, 2015

    work page 2015

  59. [59]

    Transferability in Machine Learning: from Phenomena to Black-Box Attacks using Adversarial Samples

    Papernot, N., McDaniel, P., and Goodfellow, I. Transferability in machine learning: from phenomena to black-box attacks using adversarial samples. arXiv preprint arXiv:1605.07277, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  60. [60]

    D., Chuang, C.-Y., Sra, S., and Jegelka, S

    Robinson, J. D., Chuang, C.-Y., Sra, S., and Jegelka, S. Contrastive learning with hard negative samples. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=CR1XOQ0UTh-

    work page 2021

  61. [61]

    Relaxed models for adversarial streaming: The bounded interruptions model and the advice model

    Sadigurschi, M., Shechner, M., and Stemmer, U. Relaxed models for adversarial streaming: The bounded interruptions model and the advice model. In 31st Annual European Symposium on Algorithms (ESA 2023), pp.\ 91--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023

    work page 2023

  62. [62]

    and Wygocki, P

    Sankowski, P. and Wygocki, P. Approximate nearest neighbors search without false negatives for _2 for c> n . In ISAAC, 2017

    work page 2017

  63. [63]

    Nearest-Neighbor Methods in Learning and Vision: Theory and Practice

    Shakhnarovich, G., Darrell, T., and Indyk, P. Nearest-Neighbor Methods in Learning and Vision: Theory and Practice. The MIT Press, 03 2006. ISBN 9780262256957. doi:10.7551/mitpress/4908.001.0001. URL https://doi.org/10.7551/mitpress/4908.001.0001

    work page doi:10.7551/mitpress/4908.001.0001 2006

  64. [64]

    Nearest-neighbor methods in learning and vision

    Shakhnarovich, G., Darrell, T., and Indyk, P. Nearest-neighbor methods in learning and vision. IEEE Trans. Neural Networks, 19 0 (2): 0 377, 2008

    work page 2008

  65. [65]

    Simonoff, J. S. Smoothing methods in statistics. Springer Science & Business Media, 2012

    work page 2012

  66. [66]

    Annexml: Approximate nearest neighbor search for extreme multi-label classification

    Tagami, Y. Annexml: Approximate nearest neighbor search for extreme multi-label classification. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '17, pp.\ 455–464, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 9781450348874. doi:10.1145/3097983.3097987. URL https://doi.org/10.1...

    work page doi:10.1145/3097983.3097987 2017

  67. [67]

    G., and Anderson, D

    Vasiloglou, N., Gray, A. G., and Anderson, D. V. Scalable semidefinite manifold learning. In 2008 IEEE Workshop on Machine Learning for Signal Processing, pp.\ 368--373, 2008. doi:10.1109/MLSP.2008.4685508

    work page doi:10.1109/mlsp.2008.4685508 2008

  68. [68]

    G., and Anderson, D

    Vasiloglou, N., Gray, A. G., and Anderson, D. V. Learning isometric separation maps. In 2009 IEEE International Workshop on Machine Learning for Signal Processing, pp.\ 1--6, 2009. doi:10.1109/MLSP.2009.5306212

    work page doi:10.1109/mlsp.2009.5306212 2009

  69. [69]

    Wand, M. P. and Jones, M. C. Kernel smoothing. CRC press, 1994

    work page 1994

  70. [70]

    Optimal las vegas approximate near neighbors in _p

    Wei, A. Optimal las vegas approximate near neighbors in _p . ACM Transactions on Algorithms (TALG), 18 0 (1): 0 1--27, 2022

    work page 2022

  71. [71]

    Woodruff, D. P. and Zhou, S. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp.\ 1183--1196, 2022. doi:10.1109/FOCS52979.2021.00116

    work page doi:10.1109/focs52979.2021.00116 2021

  72. [72]

    Generating adversarial examples with adversarial networks

    Xiao, C., Li, B., Zhu, J.-Y., He, W., Liu, M., and Song, D. Generating adversarial examples with adversarial networks. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, IJCAI'18, pp.\ 3905–3911. AAAI Press, 2018. ISBN 9780999241127

    work page 2018

  73. [73]

    Adversarial examples: Attacks and defenses for deep learning

    Yuan, X., He, P., Zhu, Q., and Li, X. Adversarial examples: Attacks and defenses for deep learning. IEEE transactions on neural networks and learning systems, 30 0 (9): 0 2805--2824, 2019

    work page 2019