{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:22:04Z","timestamp":1758270124137,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T00:00:00Z","timestamp":1529452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2018,6,20]]},"DOI":"10.1145\/3188745.3188846","type":"proceedings-article","created":{"date-parts":[[2018,6,20]],"date-time":"2018-06-20T20:15:46Z","timestamp":1529525746000},"page":"787-800","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Data-dependent hashing via nonlinear spectral gaps"],"prefix":"10.1145","author":[{"given":"Alexandr","family":"Andoni","sequence":"first","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Assaf","family":"Naor","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}]},{"given":"Aleksandar","family":"Nikolov","sequence":"additional","affiliation":[{"name":"University of Toronto, Canada"}]},{"given":"Ilya","family":"Razenshteyn","sequence":"additional","affiliation":[{"name":"Microsoft Research, USA"}]},{"given":"Erik","family":"Waingarten","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,6,20]]},"reference":[{"unstructured":"Alexandr Andoni. 2009. Alexandr Andoni. 2009.","key":"e_1_3_2_2_1_1"},{"doi-asserted-by":"crossref","unstructured":"Alexandr Andoni. 2010. Nearest Neighbor Search in high-dimensional spaces. (2010). Alexandr Andoni. 2010. Nearest Neighbor Search in high-dimensional spaces. (2010).","key":"e_1_3_2_2_3_1","DOI":"10.1007\/978-3-642-22993-0_1"},{"unstructured":"Invited talk at the Workshop on Barriers in Computational Complexity II http:\/\/www.mit.edu\/~andoni\/nnsbarriers.pdf. Invited talk at the Workshop on Barriers in Computational Complexity II http:\/\/www.mit.edu\/~andoni\/nnsbarriers.pdf.","key":"e_1_3_2_2_4_1"},{"unstructured":"Alexandr Andoni and Piotr Indyk. 2006. Alexandr Andoni and Piotr Indyk. 2006.","key":"e_1_3_2_2_5_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_6_1","DOI":"10.1109\/FOCS.2006.49"},{"volume-title":"Handbook of Discrete and Computational Geometry, Jacob E. Goodman, Joseph O\u2019Rourke, and Csaba D","author":"Andoni Alexandr","unstructured":"Alexandr Andoni and Piotr Indyk . 2017. Nearest Neighbors in High-Dimensional Spaces . In Handbook of Discrete and Computational Geometry, Jacob E. Goodman, Joseph O\u2019Rourke, and Csaba D . T\u00f3th (Eds.). CRC Press LLC , 1133\u20131153. Alexandr Andoni and Piotr Indyk. 2017. Nearest Neighbors in High-Dimensional Spaces. In Handbook of Discrete and Computational Geometry, Jacob E. Goodman, Joseph O\u2019Rourke, and Csaba D. T\u00f3th (Eds.). CRC Press LLC, 1133\u20131153.","key":"e_1_3_2_2_7_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_8_1","DOI":"10.5555\/1496770.1496864"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_9_1","DOI":"10.5555\/2634074.2634150"},{"key":"e_1_3_2_2_10_1","volume-title":"Proceedings of ICM 2018 (to appear).","author":"Andoni Alexandr","year":"2018","unstructured":"Alexandr Andoni , Piotr Indyk , and Ilya Razenshteyn . 2018 . Approximate Nearest Neighbor Search in High Dimensions . In Proceedings of ICM 2018 (to appear). Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. 2018. Approximate Nearest Neighbor Search in High Dimensions. In Proceedings of ICM 2018 (to appear)."},{"unstructured":"Alexandr Andoni Robert Krauthgamer and Ilya Razenshteyn. 2015. Alexandr Andoni Robert Krauthgamer and Ilya Razenshteyn. 2015.","key":"e_1_3_2_2_11_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_12_1","DOI":"10.1145\/2746539.2746552"},{"unstructured":"Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn and Erik Waingarten. 2017. Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn and Erik Waingarten. 2017.","key":"e_1_3_2_2_13_1"},{"volume-title":"Trade-offs for Approximate Near Neighbors. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192017)","author":"Time\u2013Space Optimal","unstructured":"Optimal Hashing-based Time\u2013Space Trade-offs for Approximate Near Neighbors. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192017) . 47\u201366. Available as arXiv:1608.03580. Optimal Hashing-based Time\u2013Space Trade-offs for Approximate Near Neighbors. In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192017). 47\u201366. Available as arXiv:1608.03580.","key":"e_1_3_2_2_14_1"},{"unstructured":"Alexandr Andoni Huy L. Nguyen Aleksandar Nikolov Ilya Razenshteyn and Erik Waingarten. 2017. Alexandr Andoni Huy L. Nguyen Aleksandar Nikolov Ilya Razenshteyn and Erik Waingarten. 2017.","key":"e_1_3_2_2_15_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_16_1","DOI":"10.1145\/3055399.3055418"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_17_1","DOI":"10.1145\/2746539.2746553"},{"unstructured":"Alexandr Andoni and Ilya Razenshteyn. 2016. Alexandr Andoni and Ilya Razenshteyn. 2016.","key":"e_1_3_2_2_18_1"},{"volume-title":"Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG \u20192016)","author":"Tight","unstructured":"Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG \u20192016) . 9:1\u20139:11. Available as arXiv:1507.04299. Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG \u20192016). 9:1\u20139:11. Available as arXiv:1507.04299.","key":"e_1_3_2_2_19_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_20_1","DOI":"10.4086\/toc.2012.v008a006"},{"unstructured":"Keith Ball. 1997. Keith Ball. 1997.","key":"e_1_3_2_2_21_1"},{"unstructured":"An Elementary Introduction to Modern Convex Geometry. MSRI Publications Vol. 31. Cambridge University Press. An Elementary Introduction to Modern Convex Geometry. MSRI Publications Vol. 31. Cambridge University Press.","key":"e_1_3_2_2_22_1"},{"key":"e_1_3_2_2_23_1","volume-title":"Approximate Nearest Neighbor Search for \u2113","author":"Bartal Yair","year":"2015","unstructured":"Yair Bartal and Lee-Ad Gottlieb . 2015. Approximate Nearest Neighbor Search for \u2113 p -Spaces ( 2 < p < \u221e) via Embeddings . ( 2015 ). Available as arXiv:1512.01775. Yair Bartal and Lee-Ad Gottlieb. 2015. Approximate Nearest Neighbor Search for \u2113 p -Spaces ( 2 < p < \u221e) via Embeddings. (2015). Available as arXiv:1512.01775."},{"unstructured":"Alina Beygelzimer Sham Kakade and John Langford. 2006. Alina Beygelzimer Sham Kakade and John Langford. 2006.","key":"e_1_3_2_2_24_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_25_1","DOI":"10.1145\/1143844.1143857"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_26_1","DOI":"10.1145\/3055399.3055424"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_27_1","DOI":"10.1145\/509907.509965"},{"key":"e_1_3_2_2_28_1","volume-title":"Proceedings of the Princeton conference in honor of Professor S. Bochner. 195\u2013199","author":"Cheeger Jeff","year":"1969","unstructured":"Jeff Cheeger . 1969 . A Lower Bound for the Smallest Eigenvalue of the Laplacian . In Proceedings of the Princeton conference in honor of Professor S. Bochner. 195\u2013199 . Jeff Cheeger. 1969. A Lower Bound for the Smallest Eigenvalue of the Laplacian. In Proceedings of the Princeton conference in honor of Professor S. Bochner. 195\u2013199."},{"key":"e_1_3_2_2_29_1","volume-title":"Bolyai Soc. Math. Stud.","volume":"2","author":"Chung F. R. K.","year":"1996","unstructured":"F. R. K. Chung . 1996 . Laplacians of graphs and Cheeger\u2019s inequalities. In Combinatorics, Paul Erd\u0151s is eighty, Vol. 2 (Keszthely, 1993) . Bolyai Soc. Math. Stud. , Vol. 2 . J\u00e1nos Bolyai Math. Soc., Budapest, 157\u2013172. F. R. K. Chung. 1996. Laplacians of graphs and Cheeger\u2019s inequalities. In Combinatorics, Paul Erd\u0151s is eighty, Vol. 2 (Keszthely, 1993). Bolyai Soc. Math. Stud., Vol. 2. J\u00e1nos Bolyai Math. Soc., Budapest, 157\u2013172."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_30_1","DOI":"10.1007\/PL00009449"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_31_1","DOI":"10.1007\/BF01082381"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_32_1","DOI":"10.1109\/FOCS.2010.85"},{"unstructured":"Piotr Indyk. 2001. Piotr Indyk. 2001.","key":"e_1_3_2_2_33_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_34_1","DOI":"10.1006\/jcss.2001.1781"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_35_1","DOI":"10.1145\/513400.513414"},{"key":"e_1_3_2_2_36_1","volume-title":"Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004)","author":"Indyk Piotr","year":"2004","unstructured":"Piotr Indyk . 2004 . Approximate Nearest Neighbor under Edit Distance via Product Metrics . In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004) . 646\u2013650. Piotr Indyk. 2004. Approximate Nearest Neighbor under Edit Distance via Product Metrics. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004). 646\u2013650."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_37_1","DOI":"10.1145\/276698.276876"},{"unstructured":"Piotr Indyk and Nitin Thaper. 2003. Fast Color Image Retrieval via Embeddings. (2003). Piotr Indyk and Nitin Thaper. 2003. Fast Color Image Retrieval via Embeddings. (2003).","key":"e_1_3_2_2_38_1"},{"unstructured":"Workshop on Statistical and Computational Theories of Vision (at ICCV). Workshop on Statistical and Computational Theories of Vision (at ICCV).","key":"e_1_3_2_2_39_1"},{"key":"e_1_3_2_2_40_1","volume-title":"Studies and Essays Presented to R. Courant on his 60th Birthday","author":"John Fritz","year":"1948","unstructured":"Fritz John . 1948. Extremum Problems with Inequalities as Subsidiary Conditions . In Studies and Essays Presented to R. Courant on his 60th Birthday , January 8, 1948 . Fritz John. 1948. Extremum Problems with Inequalities as Subsidiary Conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948."},{"unstructured":"Interscience Publishers Inc. New York N. Y. 187\u2013204. Interscience Publishers Inc. New York N. Y. 187\u2013204.","key":"e_1_3_2_2_41_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_42_1","DOI":"10.1145\/509907.510013"},{"key":"e_1_3_2_2_43_1","volume-title":"Lee","author":"Krauthgamer Robert","year":"2004","unstructured":"Robert Krauthgamer and James R . Lee . 2004 . Navigating Nets : Simple Algorithms for Proximity Search. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004). 798\u2013807. Robert Krauthgamer and James R. Lee. 2004. Navigating Nets: Simple Algorithms for Proximity Search. In Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192004). 798\u2013807."},{"key":"e_1_3_2_2_44_1","volume-title":"Woodruff","author":"Li Yi","year":"2014","unstructured":"Yi Li , Huy L. Nguy\u00ean , and David P . Woodruff . 2014 . On Sketching Matrix Norms and the Top Singular Vector. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192014). 1562\u20131581. Yi Li, Huy L. Nguy\u00ean, and David P. Woodruff. 2014. On Sketching Matrix Norms and the Top Singular Vector. In Proceedings of the 25th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192014). 1562\u20131581."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_45_1","DOI":"10.1145\/2897518.2897581"},{"volume-title":"19th International Workshop, APPROX \u20192016, and 20th International Workshop, RANDOM \u20192016","author":"Li Yi","unstructured":"Yi Li and David P. Woodruff . 2016. Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques , 19th International Workshop, APPROX \u20192016, and 20th International Workshop, RANDOM \u20192016 . 39:1\u2013 39:11. Yi Li and David P. Woodruff. 2016. Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 19th International Workshop, APPROX \u20192016, and 20th International Workshop, RANDOM \u20192016. 39:1\u2013 39:11.","key":"e_1_3_2_2_46_1"},{"volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP \u20192017)","author":"Li Yi","unstructured":"Yi Li and David P. Woodruff . 2017. Embeddings of Schatten Norms with Applications to Data Streams . In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP \u20192017) . 60:1\u201360:14. Yi Li and David P. Woodruff. 2017. Embeddings of Schatten Norms with Applications to Data Streams. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP \u20192017). 60:1\u201360:14.","key":"e_1_3_2_2_47_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_48_1","DOI":"10.1007\/BF02773799"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_49_1","DOI":"10.1007\/s10240-013-0053-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_50_1","DOI":"10.1215\/00127094-3119525"},{"unstructured":"Peter Bro Miltersen. 1999. Cell Probe Complexity \u2013 a Survey. In Advances in Data Structures. Peter Bro Miltersen. 1999. Cell Probe Complexity \u2013 a Survey. In Advances in Data Structures.","key":"e_1_3_2_2_51_1"},{"key":"e_1_3_2_2_52_1","volume-title":"Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u20192017)","author":"Naor Assaf","year":"2017","unstructured":"Assaf Naor . 2017 . A Spectral Gap Precludes Low-Dimensional Embeddings . In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u20192017) . 50:1\u201350:16. Assaf Naor. 2017. A Spectral Gap Precludes Low-Dimensional Embeddings. In Proceedings of the 33rd International Symposium on Computational Geometry (SoCG \u20192017). 50:1\u201350:16."},{"key":"e_1_3_2_2_53_1","volume-title":"Proceedings of ICM 2018 (to appear).","author":"Naor Assaf","year":"2018","unstructured":"Assaf Naor . 2018 . Metric Dimension Reduction: a Snapshot of the Ribe Program . In Proceedings of ICM 2018 (to appear). Assaf Naor. 2018. Metric Dimension Reduction: a Snapshot of the Ribe Program. In Proceedings of ICM 2018 (to appear)."},{"unstructured":"Assaf Naor Gilles Pisier and Gideon Schechtman. 2018. Assaf Naor Gilles Pisier and Gideon Schechtman. 2018.","key":"e_1_3_2_2_54_1"},{"volume-title":"Dimension Reduction in the Nuclear Norm. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192018)","author":"Impossibility","unstructured":"Impossibility of Dimension Reduction in the Nuclear Norm. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192018) . Impossibility of Dimension Reduction in the Nuclear Norm. In Proceedings of the 29th ACM-SIAM Symposium on Discrete Algorithms (SODA \u20192018).","key":"e_1_3_2_2_55_1"},{"key":"e_1_3_2_2_56_1","volume-title":"On Approximate Nearest Neighbor Search in \u2113 p","author":"Naor Assaf","year":"2006","unstructured":"Assaf Naor and Yuval Rabani . 2006. On Approximate Nearest Neighbor Search in \u2113 p , p > 2. ( 2006 ). Manuscript , available on request. Assaf Naor and Yuval Rabani. 2006. On Approximate Nearest Neighbor Search in \u2113 p, p > 2. (2006). Manuscript, available on request."},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_57_1","DOI":"10.1137\/05064206X"},{"unstructured":"Huy L. Nguy\u00ean. 2014. Huy L. Nguy\u00ean. 2014.","key":"e_1_3_2_2_58_1"},{"unstructured":"Algorithms for High Dimensional Data. Ph.D. Dissertation. Princeton University. Available as http:\/\/arks.princeton.edu\/ark: \/88435\/dsp01b8515q61f. Algorithms for High Dimensional Data. Ph.D. Dissertation. Princeton University. Available as http:\/\/arks.princeton.edu\/ark: \/88435\/dsp01b8515q61f.","key":"e_1_3_2_2_59_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_60_1","DOI":"10.1145\/1284320.1284322"},{"unstructured":"Ilya Razenshteyn. 2017. Ilya Razenshteyn. 2017.","key":"e_1_3_2_2_61_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_2_63_1","DOI":"10.1007\/s00013-014-0710-9"},{"unstructured":"Daniel A. Spielman. 2015. Conductance the Normalized Laplacian and Cheeger\u2019s Inequality. Lecture Notes. http:\/\/www.cs.yale.edu\/homes\/spielman\/561\/lect06- 15. pdf Daniel A. Spielman. 2015. Conductance the Normalized Laplacian and Cheeger\u2019s Inequality. Lecture Notes. http:\/\/www.cs.yale.edu\/homes\/spielman\/561\/lect06- 15. pdf","key":"e_1_3_2_2_64_1"},{"unstructured":"Andrew Chi-Chih Yao. 1981. Andrew Chi-Chih Yao. 1981.","key":"e_1_3_2_2_65_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '18","name":"STOC '18: Symposium on Theory of Computing","location":"Los Angeles CA USA"},"container-title":["Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188846","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3188745.3188846","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T07:04:17Z","timestamp":1751699057000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3188745.3188846"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,20]]},"references-count":63,"alternative-id":["10.1145\/3188745.3188846","10.1145\/3188745"],"URL":"https:\/\/doi.org\/10.1145\/3188745.3188846","relation":{},"subject":[],"published":{"date-parts":[[2018,6,20]]},"assertion":[{"value":"2018-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}