Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic

  • Original paper
  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

Given a set of n points in ℝd, the (monochromatic) Closest Pair problem asks to find a pair of distinct points in the set that are closest in the ℓp-metric. Closest Pair is a fundamental problem in Computational Geometry and understanding its fine-grained complexity in the Euclidean metric when d = ω(log n) was raised as an open question in recent works (Abboud-Rubinstein-Williams [6], Williams [48], David-Karthik-Laekhanukit [17]).

In this paper, we show that for every p ∈ ℝ≥1 ∪ {0}, under the Strong Exponential Time Hypothesis (SETH), for every ε > 0, the following holds:

  • No algorithm running in time O(n2−ε) can solve the Closest Pair problem in \(d = {\left({\log n} \right)^{{\Omega _\varepsilon}\left(1 \right)}}\) dimensions in the ℓp-metric.

  • There exists δ = δ(ε) > 0 and c = c(ε) ≥ 1 such that no algorithm running in time O(n1.5−ε) can approximate Closest Pair problem to a factor of (1 + δ) in d ≥ c log n dimensions in the ℓp-metric.

In particular, our first result is shown by establishing the computational equivalence of the bichromatic Closest Pair problem and the (monochromatic) Closest Pair problem (up to nε factor in the running time) for \(d = {\left({\log n} \right)^{{\Omega _\varepsilon}\left(1 \right)}}\) dimensions.

Additionally, under SETH, we rule out nearly-polynomial factor approximation algorithms running in subquadratic time for the (monochromatic) Maximum Inner Product problem where we are given a set of n points in no(1)-dimensional Euclidean space and are required to find a pair of distinct points in the set that maximize the inner product.

At the heart of all our proofs is the construction of a dense bipartite graph with low contact dimension, i.e., we construct a balanced bipartite graph on n vertices with n2−ε edges whose vertices can be realized as points in a \({\left({\log n} \right)^{{\Omega _\varepsilon}\left(1 \right)}}\)-dimensional Euclidean space such that every pair of vertices which have an edge in the graph are at distance exactly 1 and every other pair of vertices are at distance greater than 1. This graph construction is inspired by the construction of locally dense codes introduced by Dumer-Micciancio-Sudan [18].

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. A. E. Ashikhmin, A. Barg and S. G. Vladut: Linear codes with exponentially many light vectors, J. Comb. Theory, Ser. A96 (2001), 396–399.

    Article  MathSciNet  Google Scholar 

  2. N. Ailon and B. Chazelle: The fast johnson-lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput.39 (2009), 302–322. Preliminary version in STOC’06.

    Article  MathSciNet  Google Scholar 

  3. J. Alman, T. M. Chan and R. R. Williams: Polynomial representations of threshold functions and algorithmic applications, in: FOCS, 467–476, 2016.

  4. E. Alpaydin: Introduction to Machine Learning, The MIT Press, 2nd edition, 2010.

  5. A. Abboud, A. Rubinstein and R. Williams: Distributed PCP theorems for hardness of approximation in P, CoRR, abs/1706.06407, 2017.

  6. A. Abboud, A. Rubinstein and R. Williams: Distributed PCP theorems for hardness of approximation in P, in: FOCS, 25–36, 2017.

  7. J. Alman and R. Williams: Probabilistic polynomials and hamming nearest neighbors, in: FOCS, 136–150, 2015.

  8. J. L. Bentley: Multidimensional divide-and-conquer, Commun. ACM23 (1980), 214–229.

    Article  MathSciNet  Google Scholar 

  9. M. Ben-Or: Lower bounds for algebraic computation trees (preliminary report), in: STOC, 80–86, 1983.

  10. Y. Bilu and N. Linial: Monotone maps, sphericity and bounded second eigenvalue, J. Comb. Theory, Ser. B95 (2005), 283–299.

    Article  MathSciNet  Google Scholar 

  11. J. L. Bentley and M. I. Shamos: Divide-and-conquer in multidimensional space, in: STOC, 220–230, 1976.

  12. P. Chalermsook, M. Cygan, G. Kortsarz, B. Laekhanukit, P. Manurangsi, D. Nanongkai and L. Trevisan: From gap-eth to fpt-inapproximability: Clique, dominating set, and more, in: FOCS, 743–754, 2017.

  13. L. Chen: On the hardness of approximate and exact (bichromatic) maximum inner product, in: CCC14 1–45, 2018.

    Google Scholar 

  14. L. Chen: Toward super-polynomial size lower bounds for depth-two threshold circuits, CoRR, abs/1805.10698, 2018.

  15. E. Cohen and D. D. Lewis: Approximating matrix multiplication for pattern recognition tasks, J. Algorithms30 (1999), 211–252.

    Article  MathSciNet  Google Scholar 

  16. Q. Cheng and D. Wan: A deterministic reduction for the gap minimum distance problem, IEEE Trans. Information Theory58 (2012), 6935–6941.

    Article  MathSciNet  Google Scholar 

  17. R. David, C. S. Karthik and B. Laekhanukit: On the complexity of closest pair via polar-pair of point-sets, SIAM J. Discrete Math.33 (2019), 509–527. Preliminary version appeared in SoCG 2018.

    Article  MathSciNet  Google Scholar 

  18. I. Dumer, D. Micciancio and M. Sudan: Hardness of approximating the minimum distance of a linear code, IEEE Trans. Information Theory49 (2003), 22–37.

    Article  MathSciNet  Google Scholar 

  19. P. Frankl and H. Maehara: On the contact dimensions of graphs, Discrete & Computational Geometry3 (1988), 89–96.

    Article  MathSciNet  Google Scholar 

  20. E. N. Gilbert: A comparison of signalling alphabets, Bell System Technical Journal31 (1952), 504–522.

    Article  Google Scholar 

  21. A. Garcia and H. Stichtenoth: On the asymptotic behaviour of some towers of function fields over finite fields, Journal of Number Theory61 (1966), 248–273.

    Article  MathSciNet  Google Scholar 

  22. O. Gold and M. Sharir: Dominance products and faster algorithms for high-dimensional closest pair under L∞, CoRR, abs/1605.08107, 2016.

  23. T. Hengl: Finding the right pixel size, Computers & Geosciences32 (2006), 1283–1298.

    Article  Google Scholar 

  24. K. H. Hinrichs, J. Nievergelt and P. Schorn: Plane-sweep solves the closest pair problem elegantly, Inf. Process. Lett.26 (1988), 255–261.

    Article  MathSciNet  Google Scholar 

  25. P. Indyk, M. Lewenstein, O. Lipsky and E. Porat: Closest pair problems in very high dimensions, in: ICALP, 782–792, 2004.

  26. P. Indyk and R. Motwani: Approximate nearest neighbors: Towards removing the curse of dimensionality, in: STOC, 604–613, 1998.

  27. P. Indyk: Dimensionality reduction techniques for proximity problems, in: SODA, 371–378, 2000.

  28. R. Impagliazzo, R. Paturi and F. Zane: Which problems have strongly exponential complexity? J. Comput. Syst. Sci.63 (2001), 512–530.

    Article  MathSciNet  Google Scholar 

  29. W. Johnson and J. Lindenstrauss: Extensions of Lipschitz mappings into a Hilbert space, in: Conference in modern analysis and probability, volume 26 of Contemporary Mathematics, 189–206, American Mathematical Society, 1984.

  30. J. M. Kleinberg: Two algorithms for nearest-neighbor search in high dimensions, in: STOC, 599–608, 1997.

  31. C. S. Karthik, B. Laekhanukit and P. Manurangsi: On the parameterized complexity of approximating dominating set, in: STOC, 2018, To appear.

  32. S. Khuller and Y. Matias: A simple randomized sieve algorithm for the closest-pair problem, Inf. Comput.118 (1995), 34–37.

    Article  MathSciNet  Google Scholar 

  33. B. Lin: The parameterized complexity of the k-biclique problem, J. ACM, 65 (2018), 1–23.

    Article  MathSciNet  Google Scholar 

  34. H. Maehara: Dispersed points and geometric embedding of complete bipartite graphs, Discrete & Computational Geometry6 (1991), 57–67.

    Article  MathSciNet  Google Scholar 

  35. D. Micciancio: Locally dense codes, in: CCC, 90–97, 2014.

  36. R. Motwani, A. Naor and R. Panigrahy: Lower bounds on locality sensitive hashing, SIAM J. Discrete Math.21 (2007), 930–935.

    Article  MathSciNet  Google Scholar 

  37. R. O’Donnell, Y. Wu and Y. Zhou: Optimal lower bounds for locality-sensitive hashing (except when q is tiny), TOCT, 6 1–13, 2014.

    Article  MathSciNet  Google Scholar 

  38. J. Pach: Decomposition of multiple packing and covering, Diskrete Geometrie, 2 Kolloq. Math. Inst. Univ. Salzburg, 169–178, 1980.

  39. M. O. Rabin: Probabilistic algorithms, in: Proceedings of a Symposium on New Directions and Recent Results in Algorithms and Complexity, Computer Science Department, Carnegie-Mellon University, April 7–9, 1976, 21–39, 1976.

  40. J. Reiterman, V. Rödl and E. Sinajová: Embeddings of graphs in euclidean spaces, Discrete & Computational Geometry4 (1989), 349–364.

    Article  MathSciNet  Google Scholar 

  41. A. Rubinstein: Hardness of approximate nearest neighbor search, in: STOC, 1260–1268, 2018.

  42. M. I. Shamos and D. Hoey: Closest-point problems, in: FOCS, 151–162, 1975.

  43. H. Stichtenoth, Algebraic Function Fields and Codes, Springer Publishing Company, Incorporated, 2nd edition, 2008.

  44. G. Valiant: Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem, J. ACM2 (2015), 1–45.

    Article  MathSciNet  Google Scholar 

  45. R. R. Varshamov: Estimate of the number of signals in error correcting codes, Dokl. Akad. Nauk SSSR117 (1957), 739–741.

    MathSciNet  MATH  Google Scholar 

  46. S. Vlăduţ: Lattices with exponentially large kissing numbers, preprint arXiv:1802.00886, 2018.

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

    Article  MathSciNet  Google Scholar 

  48. R. Williams: On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity, in: SODA, 1207–1215, 2018.

  49. R. Chi-Wing Wong, Y. Tao, A. Wai-Chee Fu and X. Xiao: On efficient spatial matching, in: VLDB, 579–590, 2007.

  50. A. Chi-Chih Yao: Lower bounds for algebraic computation trees with integer inputs, SIAM J. Comput.20 (1991), 655–668. Preliminary version in FOCS’89.

    Article  MathSciNet  Google Scholar 

  51. C. T. Zahn: Graph-theoretical methods for detecting and describing gestalt clusters, IEEE Trans. Computers20 (1971), 68–86.

    Article  Google Scholar 

Download references

Acknowledgements

We are grateful to Madhu Sudan for extremely helpful and informative discussion about AG codes; in particular, Madhu pointed us to [46]. We thank Bundit Laekhanukit and Or Meir for general discussions, and the Simons Institute for their wonderful work-space. Finally, we would like to thank Lijie Chen and Orr Paradise for useful comments on the paper.

Author information

Authors and Affiliations

  1. Weizmann Institute of Science, Rehovot, Israel

    C. S. Karthik

  2. University of California, Berkeley, USA

    Pasin Manurangsi

Authors
  1. C. S. Karthik
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Pasin Manurangsi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to C. S. Karthik.

Additional information

Full version of the paper available at http://arxiv.org/abs/1812.00901

Supported by Irit Dinur’s ERC-CoG grant 772839 and BSF grant 2014371.

Supported by NSF under Grants No. CCF 1655215 and CCF 1815434.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Karthik, C.S., Manurangsi, P. On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic. Combinatorica 40, 539–573 (2020). https://doi.org/10.1007/s00493-019-4113-1

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-019-4113-1

Mathematics Subject Classification (2010)

Search

Navigation