{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T09:11:20Z","timestamp":1759741880748},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T00:00:00Z","timestamp":1588032000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T00:00:00Z","timestamp":1588032000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2020,8]]},"DOI":"10.1007\/s00493-019-4113-1","type":"journal-article","created":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T11:03:58Z","timestamp":1588071838000},"page":"539-573","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic"],"prefix":"10.1007","volume":"40","author":[{"given":"C. S.","family":"Karthik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasin","family":"Manurangsi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,4,28]]},"reference":[{"key":"4113_CR1","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1006\/jcta.2001.3206","volume":"96","author":"A E Ashikhmin","year":"2001","unstructured":"A. E. Ashikhmin, A. Barg and S. G. Vladut: Linear codes with exponentially many light vectors, J. Comb. Theory, Ser. A96 (2001), 396\u2013399.","journal-title":"J. Comb. Theory, Ser. A"},{"key":"4113_CR2","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1137\/060673096","volume":"39","author":"N Ailon","year":"2009","unstructured":"N. Ailon and B. Chazelle: The fast johnson-lindenstrauss transform and approximate nearest neighbors, SIAM J. Comput.39 (2009), 302\u2013322. Preliminary version in STOC\u201906.","journal-title":"SIAM J. Comput."},{"key":"4113_CR3","doi-asserted-by":"crossref","unstructured":"J. Alman, T. M. Chan and R. R. Williams: Polynomial representations of threshold functions and algorithmic applications, in: FOCS, 467\u2013476, 2016.","DOI":"10.1109\/FOCS.2016.57"},{"key":"4113_CR4","unstructured":"E. Alpaydin: Introduction to Machine Learning, The MIT Press, 2nd edition, 2010."},{"key":"4113_CR5","unstructured":"A. Abboud, A. Rubinstein and R. Williams: Distributed PCP theorems for hardness of approximation in P, CoRR, abs\/1706.06407, 2017."},{"key":"4113_CR6","doi-asserted-by":"crossref","unstructured":"A. Abboud, A. Rubinstein and R. Williams: Distributed PCP theorems for hardness of approximation in P, in: FOCS, 25\u201336, 2017.","DOI":"10.1109\/FOCS.2017.12"},{"key":"4113_CR7","doi-asserted-by":"crossref","unstructured":"J. Alman and R. Williams: Probabilistic polynomials and hamming nearest neighbors, in: FOCS, 136\u2013150, 2015.","DOI":"10.1109\/FOCS.2015.18"},{"key":"4113_CR8","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1145\/358841.358850","volume":"23","author":"J L Bentley","year":"1980","unstructured":"J. L. Bentley: Multidimensional divide-and-conquer, Commun. ACM23 (1980), 214\u2013229.","journal-title":"Commun. ACM"},{"key":"4113_CR9","doi-asserted-by":"crossref","unstructured":"M. Ben-Or: Lower bounds for algebraic computation trees (preliminary report), in: STOC, 80\u201386, 1983.","DOI":"10.1145\/800061.808735"},{"key":"4113_CR10","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/j.jctb.2005.04.005","volume":"95","author":"Y Bilu","year":"2005","unstructured":"Y. Bilu and N. Linial: Monotone maps, sphericity and bounded second eigenvalue, J. Comb. Theory, Ser. B95 (2005), 283\u2013299.","journal-title":"J. Comb. Theory, Ser. B"},{"key":"4113_CR11","doi-asserted-by":"crossref","unstructured":"J. L. Bentley and M. I. Shamos: Divide-and-conquer in multidimensional space, in: STOC, 220\u2013230, 1976.","DOI":"10.1145\/800113.803652"},{"key":"4113_CR12","doi-asserted-by":"crossref","unstructured":"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\u2013754, 2017.","DOI":"10.1109\/FOCS.2017.74"},{"key":"4113_CR13","first-page":"1","volume":"14","author":"L Chen","year":"2018","unstructured":"L. Chen: On the hardness of approximate and exact (bichromatic) maximum inner product, in: CCC14 1\u201345, 2018.","journal-title":"CCC"},{"key":"4113_CR14","unstructured":"L. Chen: Toward super-polynomial size lower bounds for depth-two threshold circuits, CoRR, abs\/1805.10698, 2018."},{"key":"4113_CR15","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1006\/jagm.1998.0989","volume":"30","author":"E Cohen","year":"1999","unstructured":"E. Cohen and D. D. Lewis: Approximating matrix multiplication for pattern recognition tasks, J. Algorithms30 (1999), 211\u2013252.","journal-title":"J. Algorithms"},{"key":"4113_CR16","doi-asserted-by":"publisher","first-page":"6935","DOI":"10.1109\/TIT.2012.2209198","volume":"58","author":"Q Cheng","year":"2012","unstructured":"Q. Cheng and D. Wan: A deterministic reduction for the gap minimum distance problem, IEEE Trans. Information Theory58 (2012), 6935\u20136941.","journal-title":"IEEE Trans. Information Theory"},{"key":"4113_CR17","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1137\/17M1128733","volume":"33","author":"R David","year":"2019","unstructured":"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\u2013527. Preliminary version appeared in SoCG 2018.","journal-title":"SIAM J. Discrete Math."},{"key":"4113_CR18","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1109\/TIT.2002.806118","volume":"49","author":"I Dumer","year":"2003","unstructured":"I. Dumer, D. Micciancio and M. Sudan: Hardness of approximating the minimum distance of a linear code, IEEE Trans. Information Theory49 (2003), 22\u201337.","journal-title":"IEEE Trans. Information Theory"},{"key":"4113_CR19","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/BF02187899","volume":"3","author":"P Frankl","year":"1988","unstructured":"P. Frankl and H. Maehara: On the contact dimensions of graphs, Discrete & Computational Geometry3 (1988), 89\u201396.","journal-title":"Discrete & Computational Geometry"},{"key":"4113_CR20","doi-asserted-by":"publisher","first-page":"504","DOI":"10.1002\/j.1538-7305.1952.tb01393.x","volume":"31","author":"E N Gilbert","year":"1952","unstructured":"E. N. Gilbert: A comparison of signalling alphabets, Bell System Technical Journal31 (1952), 504\u2013522.","journal-title":"Bell System Technical Journal"},{"key":"4113_CR21","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1006\/jnth.1996.0147","volume":"61","author":"A Garcia","year":"1966","unstructured":"A. Garcia and H. Stichtenoth: On the asymptotic behaviour of some towers of function fields over finite fields, Journal of Number Theory61 (1966), 248\u2013273.","journal-title":"Journal of Number Theory"},{"key":"4113_CR22","unstructured":"O. Gold and M. Sharir: Dominance products and faster algorithms for high-dimensional closest pair under L\u221e, CoRR, abs\/1605.08107, 2016."},{"key":"4113_CR23","doi-asserted-by":"publisher","first-page":"1283","DOI":"10.1016\/j.cageo.2005.11.008","volume":"32","author":"T Hengl","year":"2006","unstructured":"T. Hengl: Finding the right pixel size, Computers & Geosciences32 (2006), 1283\u20131298.","journal-title":"Computers & Geosciences"},{"key":"4113_CR24","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1016\/0020-0190(88)90150-0","volume":"26","author":"K H Hinrichs","year":"1988","unstructured":"K. H. Hinrichs, J. Nievergelt and P. Schorn: Plane-sweep solves the closest pair problem elegantly, Inf. Process. Lett.26 (1988), 255\u2013261.","journal-title":"Inf. Process. Lett."},{"key":"4113_CR25","doi-asserted-by":"crossref","unstructured":"P. Indyk, M. Lewenstein, O. Lipsky and E. Porat: Closest pair problems in very high dimensions, in: ICALP, 782\u2013792, 2004.","DOI":"10.1007\/978-3-540-27836-8_66"},{"key":"4113_CR26","doi-asserted-by":"crossref","unstructured":"P. Indyk and R. Motwani: Approximate nearest neighbors: Towards removing the curse of dimensionality, in: STOC, 604\u2013613, 1998.","DOI":"10.1145\/276698.276876"},{"key":"4113_CR27","unstructured":"P. Indyk: Dimensionality reduction techniques for proximity problems, in: SODA, 371\u2013378, 2000."},{"key":"4113_CR28","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"R. Impagliazzo, R. Paturi and F. Zane: Which problems have strongly exponential complexity? J. Comput. Syst. Sci.63 (2001), 512\u2013530.","journal-title":"J. Comput. Syst. Sci."},{"key":"4113_CR29","doi-asserted-by":"crossref","unstructured":"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\u2013206, American Mathematical Society, 1984.","DOI":"10.1090\/conm\/026\/737400"},{"key":"4113_CR30","doi-asserted-by":"crossref","unstructured":"J. M. Kleinberg: Two algorithms for nearest-neighbor search in high dimensions, in: STOC, 599\u2013608, 1997.","DOI":"10.1145\/258533.258653"},{"key":"4113_CR31","doi-asserted-by":"crossref","unstructured":"C. S. Karthik, B. Laekhanukit and P. Manurangsi: On the parameterized complexity of approximating dominating set, in: STOC, 2018, To appear.","DOI":"10.1145\/3188745.3188896"},{"key":"4113_CR32","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1006\/inco.1995.1049","volume":"118","author":"S Khuller","year":"1995","unstructured":"S. Khuller and Y. Matias: A simple randomized sieve algorithm for the closest-pair problem, Inf. Comput.118 (1995), 34\u201337.","journal-title":"Inf. Comput."},{"key":"4113_CR33","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3212622","volume":"65","author":"B Lin","year":"2018","unstructured":"B. Lin: The parameterized complexity of the k-biclique problem, J. ACM, 65 (2018), 1\u201323.","journal-title":"J. ACM"},{"key":"4113_CR34","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF02574674","volume":"6","author":"H Maehara","year":"1991","unstructured":"H. Maehara: Dispersed points and geometric embedding of complete bipartite graphs, Discrete & Computational Geometry6 (1991), 57\u201367.","journal-title":"Discrete & Computational Geometry"},{"key":"4113_CR35","doi-asserted-by":"crossref","unstructured":"D. Micciancio: Locally dense codes, in: CCC, 90\u201397, 2014.","DOI":"10.1109\/CCC.2014.17"},{"key":"4113_CR36","doi-asserted-by":"publisher","first-page":"930","DOI":"10.1137\/050646858","volume":"21","author":"R Motwani","year":"2007","unstructured":"R. Motwani, A. Naor and R. Panigrahy: Lower bounds on locality sensitive hashing, SIAM J. Discrete Math.21 (2007), 930\u2013935.","journal-title":"SIAM J. Discrete Math."},{"key":"4113_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2578221","volume":"6","author":"R O\u2019Donnell","year":"2014","unstructured":"R. O\u2019Donnell, Y. Wu and Y. Zhou: Optimal lower bounds for locality-sensitive hashing (except when q is tiny), TOCT, 6 1\u201313, 2014.","journal-title":"TOCT"},{"key":"4113_CR38","unstructured":"J. Pach: Decomposition of multiple packing and covering, Diskrete Geometrie, 2 Kolloq. Math. Inst. Univ. Salzburg, 169\u2013178, 1980."},{"key":"4113_CR39","unstructured":"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\u20139, 1976, 21\u201339, 1976."},{"key":"4113_CR40","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02187736","volume":"4","author":"J Reiterman","year":"1989","unstructured":"J. Reiterman, V. R\u00f6dl and E. Sinajov\u00e1: Embeddings of graphs in euclidean spaces, Discrete & Computational Geometry4 (1989), 349\u2013364.","journal-title":"Discrete & Computational Geometry"},{"key":"4113_CR41","doi-asserted-by":"crossref","unstructured":"A. Rubinstein: Hardness of approximate nearest neighbor search, in: STOC, 1260\u20131268, 2018.","DOI":"10.1145\/3188745.3188916"},{"key":"4113_CR42","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey: Closest-point problems, in: FOCS, 151\u2013162, 1975.","DOI":"10.1109\/SFCS.1975.8"},{"key":"4113_CR43","doi-asserted-by":"crossref","unstructured":"H. Stichtenoth, Algebraic Function Fields and Codes, Springer Publishing Company, Incorporated, 2nd edition, 2008.","DOI":"10.1007\/978-3-540-76878-4"},{"key":"4113_CR44","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2728167","volume":"2","author":"G Valiant","year":"2015","unstructured":"G. Valiant: Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem, J. ACM2 (2015), 1\u201345.","journal-title":"J. ACM"},{"key":"4113_CR45","first-page":"739","volume":"117","author":"R R Varshamov","year":"1957","unstructured":"R. R. Varshamov: Estimate of the number of signals in error correcting codes, Dokl. Akad. Nauk SSSR117 (1957), 739\u2013741.","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"4113_CR46","unstructured":"S. Vl\u0103du\u0163: Lattices with exponentially large kissing numbers, preprint arXiv:1802.00886, 2018."},{"key":"4113_CR47","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1016\/j.tcs.2005.09.023","volume":"2","author":"R Williams","year":"2005","unstructured":"R. Williams: A new algorithm for optimal 2-constraint satisfaction and its implications, Theor. Comput. Sci.2 (2005), 357\u2013365.","journal-title":"Theor. Comput. Sci."},{"key":"4113_CR48","doi-asserted-by":"crossref","unstructured":"R. Williams: On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity, in: SODA, 1207\u20131215, 2018.","DOI":"10.1137\/1.9781611975031.78"},{"key":"4113_CR49","unstructured":"R. Chi-Wing Wong, Y. Tao, A. Wai-Chee Fu and X. Xiao: On efficient spatial matching, in: VLDB, 579\u2013590, 2007."},{"key":"4113_CR50","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1137\/0220041","volume":"20","author":"A Chi-Chih Yao","year":"1991","unstructured":"A. Chi-Chih Yao: Lower bounds for algebraic computation trees with integer inputs, SIAM J. Comput.20 (1991), 655\u2013668. Preliminary version in FOCS\u201989.","journal-title":"SIAM J. Comput."},{"key":"4113_CR51","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1109\/T-C.1971.223083","volume":"20","author":"C T Zahn","year":"1971","unstructured":"C. T. Zahn: Graph-theoretical methods for detecting and describing gestalt clusters, IEEE Trans. Computers20 (1971), 68\u201386.","journal-title":"IEEE Trans. Computers"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-4113-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-019-4113-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-019-4113-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,22]],"date-time":"2022-10-22T13:00:19Z","timestamp":1666443619000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-019-4113-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,28]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["4113"],"URL":"https:\/\/doi.org\/10.1007\/s00493-019-4113-1","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,28]]},"assertion":[{"value":"7 December 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}