pith. sign in

arxiv: 2606.25887 · v1 · pith:2YR4WGEMnew · submitted 2026-06-24 · 💻 cs.CG · cs.CC

Furthest Pair Requires Quadratic Time in Superconstant Dimension under SETH

Barna Saha , Yinzhan Xu , Christopher Ye This is my paper

Pith reviewed 2026-06-25 19:17 UTC · model grok-4.3

classification 💻 cs.CG cs.CC
keywords Furthest PairSETHconditional lower boundscomputational geometryunit distance conjecturesubquadratic algorithmsdimension dependencebichromatic closest pair
0
0 comments X

The pith

Assuming SETH, Furthest Pair and related problems require n^{2-o(1)} time for any efficiently constructible superconstant dimension.

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

The paper shows that under the Strong Exponential Time Hypothesis, computing the furthest pair, bichromatic closest pair, maximum inner product, and Hopcroft's problem all require essentially quadratic time when the input dimension d grows to infinity, as long as d can be constructed efficiently. This extends an earlier conditional lower bound that applied only when d reached a specific iterated-logarithmic tower. The argument adapts a dimension-construction method originally developed in the disproof of the Erdős unit-distance conjecture to embed hard instances into every superconstant dimension without losing the quadratic hardness. If the claim holds, then the known algorithms whose running time is f(d) times n to the power 2 minus Theta of 1 over d cannot be improved in their quadratic exponent for any growing dimension.

Core claim

Under SETH, Furthest Pair, Bichromatic Closest Pair, (Bichromatic) Maximum Inner Product, and Hopcroft's Problem all require n^{2-o(1)} time whenever the dimension d equals omega of 1 and is efficiently constructible. The proof lifts the reduction of Chen (2020) by using the dimension-construction technique from the recent disproof of the Erdős unit-distance conjecture, thereby removing the restriction to dimensions of size 2 to the Theta of log star n.

What carries the argument

The dimension-construction technique from the Erdős unit-distance disproof, which produces hard point sets in every efficiently constructible superconstant dimension while preserving the SETH-based quadratic lower bound.

Load-bearing premise

The reduction and dimension-construction technique inherited from the Erdős unit-distance disproof extend without additional loss to every efficiently constructible superconstant d.

What would settle it

An algorithm that solves Furthest Pair in O(n^{2-ε}) time for some fixed ε greater than 0 when d equals log log n would refute the claimed lower bound.

Figures

Figures reproduced from arXiv: 2606.25887 by Barna Saha, Christopher Ye, Yinzhan Xu.

Figure 1
Figure 1. Figure 1: Some code snippets of the Lean 4 formalization. [PITH_FULL_IMAGE:figures/full_fig_p044_1.png] view at source ↗
read the original abstract

Several fundamental problems in computational geometry admit algorithms with running time $f(d) \cdot n^{2-\Theta(1/d)}$ for $n$ points in $d$ dimensions, making them among the most prominent examples of barely subquadratic computation. Notable members of this class include Furthest Pair, Bichromatic Closest Pair, (Bichromatic) Maximum Innter Product, and Hopcroft's Problem. Chen [Theory Comput. 2020] proved that, assuming the Strong Exponential Time Hypothesis (SETH), these problems require $n^{2-o(1)}$ time when the dimension satisfies $d=2^{\Theta(\log^* n)}$. We extend this lower bound to all efficiently constructible dimensions $d=\omega(1)$. Thus, assuming SETH, the dependence of the best known algorithms on the dimension is essentially unavoidable. The proof utilizes techniques in OpenAI's recent disproof of the Erdos unit distance conjecture. The proof was initially discovered by ChatGPT 5.5 Pro. The authors have validated and substantially edited the proof to improve the presentation.

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 paper claims that, assuming SETH, Furthest Pair (along with Bichromatic Closest Pair, Maximum Inner Product, and Hopcroft's Problem) requires n^{2-o(1)} time whenever the dimension d=ω(1) is efficiently constructible. This extends Chen (Theory Comput. 2020), which obtained the same bound only for the narrower regime d=2^Θ(log* n), by importing dimension-lifting techniques from the recent disproof of the Erdős unit-distance conjecture.

Significance. If the reduction preserves the o(1) loss for every efficiently constructible superconstant d, the result would show that the known f(d)·n^{2-Θ(1/d)} algorithms are essentially optimal in their dimension dependence under SETH, closing an important gap between the iterated-log regime and arbitrary ω(1) dimensions.

major comments (2)
  1. [Main reduction and proof of the main theorem] The central claim requires that the dimension-lifting technique (inherited from the unit-distance disproof and applied on top of Chen 2020) produces, for every efficiently constructible d=ω(1), a reduction whose SETH-based hardness carries through with only o(1) loss in the quadratic exponent. No explicit parameter tracking or loss analysis for the general case is visible.
  2. [Section describing the dimension construction] The unit-distance construction is known to be sensitive to the precise growth rate of the dimension parameter; the manuscript must rule out the possibility that the lifting introduces an extra 1/ω(1) or polyloglog factor that would weaken the bound to n^{2-ω(1)}.
minor comments (2)
  1. [Abstract and introduction] Define 'efficiently constructible' formally (e.g., time to produce the point set or the dimension parameter) so that the scope of the result is unambiguous.
  2. [Introduction] Add a short paragraph comparing the new construction's parameter dependence with the specific iterated-log regime of Chen 2020.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful comments. The concerns about explicit parameter tracking in the dimension-lifting step are well-taken; we will strengthen the manuscript with a dedicated analysis subsection. Below we respond point by point.

read point-by-point responses

  1. Referee: [Main reduction and proof of the main theorem] The central claim requires that the dimension-lifting technique (inherited from the unit-distance disproof and applied on top of Chen 2020) produces, for every efficiently constructible d=ω(1), a reduction whose SETH-based hardness carries through with only o(1) loss in the quadratic exponent. No explicit parameter tracking or loss analysis for the general case is visible.

    Authors: We agree that the current write-up would benefit from more explicit tracking. The lifting inherits the slow-growing dimension schedule from the unit-distance construction, which can be tuned (via the efficient constructibility assumption) so that the multiplicative overhead in the exponent is absorbed into the o(1) term inherited from Chen's base reduction. In the revision we will insert a new lemma that explicitly composes the loss functions, confirming that for any ω(1) growth rate that admits an efficient construction the overall loss remains o(1). revision: yes

  2. Referee: [Section describing the dimension construction] The unit-distance construction is known to be sensitive to the precise growth rate of the dimension parameter; the manuscript must rule out the possibility that the lifting introduces an extra 1/ω(1) or polyloglog factor that would weaken the bound to n^{2-ω(1)}.

    Authors: The construction parameters are chosen so that any polyloglog overhead is dominated by the ω(1) term; because the base dimension in Chen's reduction already grows faster than any iterated logarithm, the additional factor contributed by the lifting stays inside the o(1) slack. We will add a short paragraph (with a concrete inequality) that rules out an extra 1/ω(1) loss under the efficient-constructibility hypothesis. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation extends external results without reduction to inputs

full rationale

The paper's central claim extends Chen (Theory Comput. 2020) lower bound from a specific iterated-log dimension regime to all efficiently constructible ω(1) dimensions by importing techniques from an external OpenAI unit-distance disproof. No self-definitional equations, no parameters fitted to data then relabeled as predictions, and no load-bearing self-citations appear. The argument is anchored in the external SETH hypothesis plus the cited unit-distance construction; the generalization step does not reduce by construction to the paper's own fitted values or prior self-referential claims.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the validity of SETH and on the transfer of the unit-distance disproof technique to the geometric reduction for arbitrary superconstant dimensions.

axioms (1)
  • domain assumption Strong Exponential Time Hypothesis (SETH)
    Standard assumption used to derive conditional lower bounds for fine-grained problems; invoked to obtain the n^{2-o(1)} requirement.

pith-pipeline@v0.9.1-grok · 5722 in / 1175 out tokens · 14200 ms · 2026-06-25T19:17:45.597245+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

68 extracted references

  1. [1]

    Aristotle: Imo-level automated theorem proving, 2025

    Tudor Achim, Alex Best, Alberto Bietti, Kevin Der, Mathïs Fédérico, Sergei Gukov, Daniel Halpern-Leistner, Kirsten Henningsgard, Yury Kudryashov, Alexander Meiburg, Martin Michelsen, Riley Patterson, Eric Rodriguez, Laura Scharff, Vikram Shanker, Vladmir Sicca, Hari Sowrirajan, Aidan Swope, Matyas Tamas, Vlad Tenev, Jonathan Thomm, Harold Williams, and La...

    2025

  2. [2]

    Quantum algorithms for hopcroft's problem

    Vladimirs Andrejevs, Aleksandrs Belovs, and Jevgenijs Vihrovs. Quantum algorithms for hopcroft's problem. In Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS) , pages 9:1--9:16, 2024

    2024

  3. [3]

    Algorithms and hardness for linear algebra on geometric graphs

    Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. Algorithms and hardness for linear algebra on geometric graphs. In Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science (FOCS) , pages 541--552, 2020

    2020

  4. [4]

    Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl

    Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean minimum spanning trees and bichromatic closest pairs. In Proceedings of the 6th Annual Symposium on Computational Geometry (SoCG) , pages 203--210, 1990

    1990

  5. [5]

    Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions

    Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Commun. ACM , 51(1):117--122, 2008

    2008

  6. [6]

    Razenshteyn, and Ludwig Schmidt

    Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt. Practical and optimal LSH for angular distance. In Proceedings of the 29th Annual Conference on Neural Information Processing Systems , pages 1225--1233, 2015

    2015

  7. [7]

    Nguyen, and Ilya P

    Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya P. Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1018--1028, 2014

    2014

  8. [8]

    Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing

    Josh Alman, Jiehao Liang, Zhao Song, Ruizhe Zhang, and Danyang Zhuo. Bypass exponential time preprocessing: Fast neural network training via weight-data correlation preprocessing. In Proceedings of the 37th Annual Conference on Neural Information Processing Systems (NeurIPS) , 2023

    2023

  9. [9]

    Introduction to commutative algebra

    Michael F Atiyah and Ian Grant Macdonald. Introduction to commutative algebra . CRC press, 2018

    2018

  10. [10]

    Razenshteyn, and Francesco Silvestri

    Thomas Dybdahl Ahle, Rasmus Pagh, Ilya P. Razenshteyn, and Francesco Silvestri. On the complexity of inner product similarity join. In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) , pages 151--164, 2016

    2016

  11. [11]

    Razenshteyn

    Alexandr Andoni and Ilya P. Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC) , pages 793--801, 2015

    2015

  12. [12]

    Probabilistic polynomials and hamming nearest neighbors

    Josh Alman and Ryan Williams. Probabilistic polynomials and hamming nearest neighbors. In Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS) , pages 136--150, 2015

    2015

  13. [13]

    Divide-and-conquer in multidimensional space

    Jon Louis Bentley and Michael Ian Shamos. Divide-and-conquer in multidimensional space. In Proceedings of the 8th Annual ACM Symposium on Theory of Computing (STOC) , pages 220--230, 1976

    1976

  14. [14]

    Cutting hyperplanes for divide-and-conquer

    Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discret. Comput. Geom. , 9:145--158, 1993

    1993

  15. [15]

    On the hardness of approximate and exact (bichromatic) maximum inner product

    Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. Theory Comput. , 16:1--50, 2020

    2020

  16. [16]

    A framework for similarity search with space-time tradeoffs using locality-sensitive filtering

    Tobias Christiani. A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 31--46, 2017

    2017

  17. [17]

    Fast and robust shape diameter function

    Shuangmin Chen, Taijun Liu, Zhenyu Shu, Shiqing Xin, Ying He, and Changhe Tu. Fast and robust shape diameter function. Plos one , 13(1):e0190666, 2018

    2018

  18. [18]

    Closest pair queries in spatial databases

    Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, and Michael Vassilakopoulos. Closest pair queries in spatial databases. In Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data , pages 189--200, 2000

    2000

  19. [19]

    Algorithms for processing k-closest-pair queries in spatial databases

    Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, and Michael Vassilakopoulos. Algorithms for processing k-closest-pair queries in spatial databases. Data Knowl. Eng. , 49(1):67--104, 2004

    2004

  20. [20]

    Set similarity search beyond minhash

    Tobias Christiani and Rasmus Pagh. Set similarity search beyond minhash. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC) , pages 1094--1107, 2017

    2017

  21. [21]

    Chan and Da Wei Zheng

    Timothy M. Chan and Da Wei Zheng. Hopcroft's problem, log* shaving, two-dimensional fractional cascading, and decision trees. ACM Trans. Algorithms , 20(3):24, 2024

    2024

  22. [22]

    Dummit and Richard M

    David S. Dummit and Richard M. Foote. Abstract algebra . John Wiley & Sons, 3rd edition, 2004

    2004

  23. [23]

    A reliable randomized algorithm for the closest-pair problem

    Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closest-pair problem. J. Algorithms , 25(1):19--51, 1997

    1997

  24. [24]

    Fast hierarchical clustering and other applications of dynamic closest pairs

    David Eppstein. Fast hierarchical clustering and other applications of dynamic closest pairs. ACM J. Exp. Algorithmics , 5:1, 2000

    2000

  25. [25]

    On sets of distances of n points

    Paul Erd o s. On sets of distances of n points. The American Mathematical Monthly , 53(5):248--250, 1946

    1946

  26. [26]

    On the relative complexities of some geometric problems

    Jeff Erickson. On the relative complexities of some geometric problems. In Proceedings of the 7th Canadian Conference on Computational Geometry (CCCG) , pages 85--90, 1995

    1995

  27. [27]

    Enhancing spatialhadoop with closest pair queries

    Francisco Garc \' a - Garc \' a, Antonio Corral, Luis Iribarne, Michael Vassilakopoulos, and Yannis Manolopoulos. Enhancing spatialhadoop with closest pair queries. In Proceedings of the 20th East European Conference on Advances in Databases and Information Systems (ADBIS) , pages 212--225, 2016

    2016

  28. [28]

    Subquadratic algorithms and hardness for attention with any temperature

    Shreya Gupta, Boyang Huang, Barna Saha, Yinzhan Xu, and Christopher Ye. Subquadratic algorithms and hardness for attention with any temperature. In The Fourteenth International Conference on Learning Representations (ICLR) , 2026

    2026

  29. [29]

    Gilbert, Daniel W

    Elmer G. Gilbert, Daniel W. Johnson, and S. Sathiya Keerthi. A fast procedure for computing the distance between complex objects in three-dimensional space. IEEE J. Robotics Autom. , 4(2):193--203, 1988

    1988

  30. [30]

    Gonzalez

    Teofilo F. Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical computer science , 38:293--306, 1985

    1985

  31. [31]

    Golod and Igor R

    Evgeniy S. Golod and Igor R. Shafarevich. On the class field tower. Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya , 28(2):261--272, 1964

    1964

  32. [32]

    Golod and Igor R

    Evgeniy S. Golod and Igor R. Shafarevich. On class field towers. In Fourteen Papers on Logic, Algebra, Complex Variables and Topology , volume 48 of American Mathematical Society Translations, Series 2 , pages 91--102. American Mathematical Society, 1965. English translation of the 1964 Russian paper

    1965

  33. [33]

    A practical approach for computing the diameter of a point set

    Sariel Har - Peled. A practical approach for computing the diameter of a point set. In Proceedings of the 17th Annual Symposium on Computational Geometry (SoCG) , pages 177--186, 2001

    2001

  34. [34]

    Approximate nearest neighbor: Towards removing the curse of dimensionality

    Sariel Har - Peled, Piotr Indyk, and Rajeev Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory Comput. , 8(1):321--350, 2012

    2012

  35. [35]

    A faster subquadratic algorithm for finding outlier correlations

    Matti Karppa, Petteri Kaski, and Jukka Kohonen. A faster subquadratic algorithm for finding outlier correlations. ACM Trans. Algorithms , 14(3):31:1--31:26, 2018

    2018

  36. [36]

    A simple randomized sieve algorithm for the closest-pair problem

    Samir Khuller and Yossi Matias. A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput. , 118(1):34--37, 1995

    1995

  37. [37]

    Lin and John F

    Ming C. Lin and John F. Canny. A fast algorithm for incremental distance calculation. In Proceedings of the 1991 IEEE International Conference on Robotics and Automation , pages 1008--1014, 1991

    1991

  38. [38]

    Daniel A. Marcus. Number fields . Springer, 2nd edition, 2018

    2018

  39. [39]

    Efficient partition trees

    Jir \' Matousek. Efficient partition trees. Discret. Comput. Geom. , 8:315--334, 1992

    1992

  40. [40]

    Range searching with efficient hiearchical cutting

    Jir \' Matousek. Range searching with efficient hiearchical cutting. Discret. Comput. Geom. , 10:157--182, 1993

    1993

  41. [41]

    Daniel C. Mayer. New number fields with known p-class tower. Tatra Mountains Math. Publ , 64:21--57, 2015

    2015

  42. [42]

    Computing the diameter of a point set

    Gr \' e goire Malandain and Jean - Daniel Boissonnat. Computing the diameter of a point set. Int. J. Comput. Geom. Appl. , 12(6):489--510, 2002

    2002

  43. [43]

    James S. Milne. Fields and galois theory. Courses Notes, Version , 4, 2003

    2003

  44. [44]

    James S. Milne. Algebraic number theory, 2020

    2020

  45. [45]

    Enhancing the slicenbound algorithm for the closest-pairs query with binary space partitioning

    George Mavrommatis, Panagiotis Moutafis, and Antonio Corral. Enhancing the slicenbound algorithm for the closest-pairs query with binary space partitioning. In Proceedings of the 25th Pan-Hellenic Conference on Informatics (PCI) , pages 107--112. ACM , 2021

    2021

  46. [46]

    Algebraic number theory , volume 322

    J \"u rgen Neukirch. Algebraic number theory , volume 322. Springer Science & Business Media, 2013

    2013

  47. [47]

    On symmetric and asymmetric lshs for inner product search

    Behnam Neyshabur and Nathan Srebro. On symmetric and asymmetric lshs for inner product search. In Proceedings of the 32nd International Conference on Machine Learning (ICML) , pages 1926--1934, 2015

    1926

  48. [48]

    C\( ^ 2 \)p: Clustering based on closest pairs

    Alexandros Nanopoulos, Yannis Theodoridis, and Yannis Manolopoulos. C\( ^ 2 \)p: Clustering based on closest pairs. In Proceedings of 27th International Conference on Very Large Data Bases (VLDB) , pages 331--340, 2001

    2001

  49. [49]

    Planar point sets with many unit distances, 2026

    OpenAI. Planar point sets with many unit distances, 2026. Available at https://cdn.openai.com/pdf/74c24085-19b0-4534-9c90-465b8e29ad73/unit-distance-proof.pdf

    2026

  50. [50]

    Parikshit Ram and Alexander G. Gray. Maximum inner-product search using cone trees. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD) , pages 931--939, 2012

    2012

  51. [51]

    Lin, Dinesh Manocha, and Young J

    Stephane Redon, Ming C. Lin, Dinesh Manocha, and Young J. Kim. Fast continuous collision detection for articulated models. J. Comput. Inf. Sci. Eng. , 5(2):126--137, 2005

    2005

  52. [52]

    Random features for large-scale kernel machines

    Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceedings of the 21st Annual Conference on Neural Information Processing Systems , pages 1177--1184, 2007

    2007

  53. [53]

    S afarevi c

    Igor R. S afarevi c . Extensions \`a points de ramification donn \'e s (en russe). Publications Math \'e matiques de l'IH \'E S , 18:71--92, 1963

    1963

  54. [54]

    Closest-point problems

    Michael Ian Shamos and Dan Hoey. Closest-point problems. In Proceedings of the 16th Annual Symposium on Foundations of Computer Science (FOCS) , pages 151--162, 1975

    1975

  55. [55]

    Shafarevich

    Igor R. Shafarevich. Extensions with given points of ramification. Amer. Math. Soc. Translation, Ser , 2(59):128--149, 1966

    1966

  56. [56]

    Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS)

    Anshumali Shrivastava and Ping Li. Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS) . In Proceedings of the 28th Annual Conference on Neural Information Processing Systems , pages 2321--2329, 2014

    2014

  57. [57]

    Asymmetric minwise hashing for indexing binary inner products and set containment

    Anshumali Shrivastava and Ping Li. Asymmetric minwise hashing for indexing binary inner products and set containment. In Proceedings of the 24th International Conference on World Wide Web (WWW) , pages 981--991, 2015

    2015

  58. [58]

    Consistent mesh partitioning and skeletonisation using the shape diameter function

    Lior Shapira, Ariel Shamir, and Daniel Cohen - Or. Consistent mesh partitioning and skeletonisation using the shape diameter function. Vis. Comput. , 24(4):249--259, 2008

    2008

  59. [59]

    Exact and approximate maximum inner product search with LEMP

    Christina Teflioudi and Rainer Gemulla. Exact and approximate maximum inner product search with LEMP . ACM Trans. Database Syst. , 42(1):5:1--5:49, 2017

    2017

  60. [60]

    Lean 4 formalization of the disproof of Erd o s's planar unit-distance conjecture , 2026

    The Erd o s unit-distance formalization contributors . Lean 4 formalization of the disproof of Erd o s's planar unit-distance conjecture , 2026. https://github.com/logical-intelligence/erdos-unit-distance

    2026

  61. [61]

    Toussaint

    Godfried T. Toussaint. Solving geometric problems with the rotating calipers. In Proc. IEEE Melecon , volume 83, page A10, 1983

    1983

  62. [62]

    Die bestimmung der dichtigkeit einer menge von primzahlen, welche zu einer gegebenen substitutionsklasse geh \"o ren

    Nikolaj Tschebotareff. Die bestimmung der dichtigkeit einer menge von primzahlen, welche zu einer gegebenen substitutionsklasse geh \"o ren. Mathematische Annalen , 95(1):191--228, 1926

    1926

  63. [63]

    Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem

    Gregory Valiant. Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem. J. ACM , 62(2):13:1--13:45, 2015

    2015

  64. [64]

    A new algorithm for optimal 2-constraint satisfaction and its implications

    Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications. Theor. Comput. Sci. , 348(2-3):357--365, 2005

    2005

  65. [65]

    On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity

    Ryan Williams. On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1207--1215, 2018

    2018

  66. [66]

    Part iii profinite groups

    Gareth Wilkes. Part iii profinite groups. Lecture notes, University of Cambridge, 2020. Available at https://www.dpmms.cam.ac.uk/ grw46/LectureNotes.pdf

    2020

  67. [67]

    Efficient similarity joins for near-duplicate detection

    Chuan Xiao, Wei Wang, Xuemin Lin, Jeffrey Xu Yu, and Guoren Wang. Efficient similarity joins for near-duplicate detection. ACM Transactions on Database Systems (TODS) , 36(3):1--41, 2011

    2011

  68. [68]

    On constructing minimum spanning trees in k-dimensional spaces and related problems

    Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM Journal on Computing , 11(4):721--736, 1982

    1982