{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:40Z","timestamp":1781031460994,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"NSF","award":["CCF2008733"],"award-info":[{"award-number":["CCF2008733"]}]},{"name":"ONR","award":["N00014-22-1-2713"],"award-info":[{"award-number":["N00014-22-1-2713"]}]},{"name":"ERC Starting Grant","award":["101039914"],"award-info":[{"award-number":["101039914"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800856","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1477-1488","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximate Orthogonal Vectors and Diameter via Regularity Lemma"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-8042-0976","authenticated-orcid":false,"given":"Alexandr","family":"Andoni","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2226-7980","authenticated-orcid":false,"given":"Shunhua","family":"Jiang","sequence":"additional","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6814-3918","authenticated-orcid":false,"given":"Stepan","family":"Zharkov","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","series-title":"SIAM Symposium on Simplicity in Algorithms (SOSA)","volume-title":"Faster algorithms for average-case orthogonal vectors and closest pair problems","author":"Alman Josh","year":"2025","unstructured":"Josh Alman, Alexandr Andoni, and Hengjie Zhang. Faster algorithms for average-case orthogonal vectors and closest pair problems. In SIAM Symposium on Simplicity in Algorithms (SOSA). SIAM, 2025."},{"key":"e_1_3_2_1_2_1","first-page":"476","volume-title":"2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Alman Josh","unstructured":"Josh Alman, Timothy M Chan, and Ryan Williams. Polynomial representations of threshold functions and algorithmic applications. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 467\u2013476. IEEE, 2016."},{"key":"e_1_3_2_1_3_1","first-page":"649","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Alman Josh","unstructured":"Josh Alman, Timothy M Chan, and Ryan Williams. Faster deterministic and las vegas algorithms for offline approximate nearest neighbors in high dimensions. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 637\u2013649. SIAM, 2020."},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Andoni Alexandr","year":"2014","unstructured":"Alexandr Andoni, Piotr Indyk, Huy L. Nguyen, and Ilya Razenshteyn. Beyond locality-sensitive hashing. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2014. Full version at http:\/\/arxiv.org\/abs\/1306.1547."},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the International Congress of Mathematicians (ICM) 2018, pages 3287\u20133318. World Scientific, 2018. This survey accompanied the ICM 2018 talk of Piotr Indyk. arXiv preprint arXiv:1806","author":"Andoni Alexandr","unstructured":"Alexandr Andoni, Piotr Indyk, and Ilya Razenshteyn. Approximate nearest neighbor search in high dimensions. In Proceedings of the International Congress of Mathematicians (ICM) 2018, pages 3287\u20133318. World Scientific, 2018. This survey accompanied the ICM 2018 talk of Piotr Indyk. arXiv preprint arXiv:1806.09823."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC)","author":"Andoni Alexandr","year":"2025","unstructured":"Alexandr Andoni, Shunhua Jiang, and Omri Weinstein. A framework for building data structures from communication protocols. In Proceedings of the Symposium on Theory of Computing (STOC), 2025."},{"key":"e_1_3_2_1_7_1","first-page":"739","volume-title":"2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)","author":"Ahle Thomas D","unstructured":"Thomas D Ahle and Jakob BT Knudsen. Subsets and supermajorities: Optimal hashing-based set similarity search. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 728\u2013739. IEEE, 2020."},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Andoni Alexandr","year":"2017","unstructured":"Alexandr Andoni, Thijs Laarhoven, Ilya P. Razenshteyn, and Erik Waingarten. Optimal hashing-based time-space trade-offs for approximate near neighbors. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(92)90001-9"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC)","author":"Andoni Alexandr","year":"2018","unstructured":"Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, and Erik Waingarten. Data-dependent hashing via nonlinear spectral gaps. In Proceedings of the Symposium on Theory of Computing (STOC), 2018."},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS)","author":"Andoni Alexandr","year":"2018","unstructured":"Alexandr Andoni, Assaf Naor, Aleksandar Nikolov, Ilya P. Razenshteyn, and Erik Waingarten. Holder homeomorphisms and approximate nearest neighbors. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2018."},{"key":"e_1_3_2_1_12_1","first-page":"1190","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Andoni Alexandr","unstructured":"Alexandr Andoni, Aleksandar Nikolov, Ilya P. Razenshteyn, and Erik Waingarten. Approximate nearest neighbors beyond space partitions. In D\u00e1niel Marx, editor, Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1171\u20131190. SIAM, 2021."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC)","author":"Andoni Alexandr","year":"2015","unstructured":"Alexandr Andoni and Ilya Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In Proceedings of the Symposium on Theory of Computing (STOC), 2015. Full version at http:\/\/arxiv.org\/abs\/1501.01062."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the ACM Symposium on Computational Geometry (SoCG)","author":"Andoni Alexandr","year":"2016","unstructured":"Alexandr Andoni and Ilya Razenshteyn. Tight lower bounds for data-dependent locality-sensitive hashing. In Proceedings of the ACM Symposium on Computational Geometry (SoCG), 2016. Available at http:\/\/arxiv.org\/abs\/1507.04299."},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Andoni Alexandr","year":"2017","unstructured":"Alexandr Andoni, Ilya Razenshteyn, and Negev Shekel Nosatzki. Lsh forest: Practical algorithms made theoretical. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017."},{"key":"e_1_3_2_1_16_1","first-page":"36","volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Abboud Amir","unstructured":"Amir Abboud, Aviad Rubinstein, and Ryan Williams. Distributed pcp theorems for hardness of approximation in p. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 25\u201336. IEEE, 2017."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2024.114976"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9846-4"},{"key":"e_1_3_2_1_19_1","first-page":"230","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud, Ryan Williams, and Huacheng Yu. More applications of the polynomial method to algorithm design. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA 2014), pages 218\u2013230. SIAM, 2014."},{"key":"e_1_3_2_1_20_1","volume-title":"International Conference on Learning Representations","author":"Alman Josh","year":"2025","unstructured":"Josh Alman and Hantao Yu. Fundamental limitations on subquadratic alternatives to transformers. In International Conference on Learning Representations, 2025."},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS)","author":"Bao Yiqiao","year":"2025","unstructured":"Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, and Tian Zhang. Average-distortion sketching. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2025."},{"key":"e_1_3_2_1_22_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"B\u0103doiu M.","year":"2003","unstructured":"M. B\u0103doiu and K. Clarkson. Smaller core-sets for balls. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003."},{"key":"e_1_3_2_1_23_1","first-page":"147","volume-title":"9th ACM-SIAM Sympos. Discrete Algorithms","author":"Bespamyatnikh S.N.","year":"1998","unstructured":"S.N. Bespamyatnikh. An efficient algorithm for the three-dimensional diameter problem. In 9th ACM-SIAM Sympos. Discrete Algorithms, pages 136\u2013147, 1998."},{"key":"e_1_3_2_1_24_1","volume-title":"Paper 2024\/637","author":"Ball Marshall","year":"2024","unstructured":"Marshall Ball, Juan Garay, Peter Hall, Aggelos Kiayias, and Giorgos Panagiotakos. Towards permissionless consensus in the standard model via fine-grained complexity. Cryptology ePrint Archive, Paper 2024\/637, 2024."},{"key":"e_1_3_2_1_25_1","first-page":"404","volume-title":"Proceedings of the Sixth International World Wide Web Conference","author":"Broder Andrei","year":"1997","unstructured":"Andrei Broder, Steve Glassman, Mark Manasse, and Geoffrey Zweig. Syntactic clustering of the web. Proceedings of the Sixth International World Wide Web Conference, pages 391\u2013404, 1997."},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC)","author":"Backurs Arturs","year":"2015","unstructured":"Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the Symposium on Theory of Computing (STOC), 2015."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the Symposium on Theory of Computing","author":"Borodin Allan","year":"1999","unstructured":"Allan Borodin, Rafail Ostrovsky, and Yuval Rabani. Subquadratic approximation algorithms for clustering problems in high dimensional spaces. Proceedings of the Symposium on Theory of Computing, 1999."},{"key":"e_1_3_2_1_28_1","volume-title":"36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019","author":"Bringmann Karl","year":"2019","unstructured":"Karl Bringmann. Fine-grained complexity theory (tutorial). In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik, 2019."},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of FUN","author":"Broder Andei","year":"1998","unstructured":"Andei Broder. Filtering near-duplicate documents. Proceedings of FUN, 1998."},{"key":"e_1_3_2_1_30_1","first-page":"496","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC)","author":"Ball Marshall","year":"2017","unstructured":"Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan. Average-case fine-grained hardness. In Proceedings of the Symposium on Theory of Computing (STOC), pages 483\u2013496, 2017."},{"key":"e_1_3_2_1_31_1","first-page":"388","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC)","author":"Charikar Moses","year":"2002","unstructured":"Moses Charikar. Similarity estimation techniques from rounding. In Proceedings of the Symposium on Theory of Computing (STOC), pages 380\u2013388, 2002."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-019-00062-5"},{"issue":"1","key":"e_1_3_2_1_33_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2020.v016a004","article-title":"On the hardness of approximate and exact (bichromatic) maximum inner product","volume":"16","author":"Chen Lijie","year":"2020","unstructured":"Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. Theory of Computing, 16(1):1\u201350, 2020.","journal-title":"Theory of Computing"},{"key":"e_1_3_2_1_34_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Christiani Tobias","year":"2017","unstructured":"Tobias Christiani. A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017."},{"key":"e_1_3_2_1_35_1","volume-title":"Springer","author":"Charikar Moses","year":"2002","unstructured":"Moses Charikar, Piotr Indyk, and Rina Panigrahy. New algorithms for subset query, partial match, orthogonal range searching, and related problems. In International Colloquium on Automata, Languages, and Programming, pages 451\u2013462. Springer, 2002."},{"key":"e_1_3_2_1_36_1","first-page":"1107","volume-title":"Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing","author":"Christiani Tobias","unstructured":"Tobias Christiani and Rasmus Pagh. Set similarity search beyond minhash. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1094\u20131107. ACM, 2017."},{"key":"e_1_3_2_1_37_1","first-page":"1255","volume-title":"Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA","author":"Chan Timothy M","year":"2016","unstructured":"Timothy M Chan and Ryan Williams. Deterministic apsp, orthogonal vectors, and more: Quickly derandomizing razborov-smolensky. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA 2016), pages 1246\u20131255. SIAM, 2016."},{"key":"e_1_3_2_1_38_1","first-page":"40","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Chen Lijie","unstructured":"Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 21\u201340. SIAM, 2019."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03427-9"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Gajulapalli Karthik","year":"2026","unstructured":"Karthik Gajulapalli, Alexander Golovnev, Samuel King, and Sidhant Saraogi. Online orthogonal vectors revisited. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2026."},{"key":"e_1_3_2_1_42_1","first-page":"778","volume-title":"SODA","volume":"1","author":"Goel Ashish","year":"2001","unstructured":"Ashish Goel, Piotr Indyk, and Kasturi R Varadarajan. Reductions among high dimensional proximity problems. In SODA, volume 1, pages 769\u2013778, 2001."},{"key":"e_1_3_2_1_43_1","first-page":"10","volume-title":"33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Halld\u00f3rsson Magn\u00fas M.","year":"2025","unstructured":"Magn\u00fas M. Halld\u00f3rsson, Nicolaos Matsakis, and Pavel Vesel\u00fd. Streaming Diameter of High-Dimensional Points. In Anne Benoit, Haim Kaplan, Sebastian Wild, and Grzegorz Herman, editors, 33rd Annual European Symposium on Algorithms (ESA 2025), volume 351 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1\u201358:10, Dagstuhl, Germany, 2025. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_44_1","first-page":"155","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS)","author":"Indyk Piotr","year":"1998","unstructured":"Piotr Indyk. On approximate nearest neighbors in non-Euclidean spaces. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), pages 148\u2013155, 1998."},{"key":"e_1_3_2_1_45_1","volume-title":"Proceedings of the Ninth ACM-SIAM Symposium on Discrete Algorithms","author":"Indyk Piotr","year":"2000","unstructured":"Piotr Indyk. Dimensionality reduction techniques for proximity problems. Proceedings of the Ninth ACM-SIAM Symposium on Discrete Algorithms, 2000."},{"key":"e_1_3_2_1_46_1","unstructured":"Piotr Indyk. High-dimensional computational geometry. Ph.D. Thesis. Department of Computer Science Stanford University 2001."},{"key":"e_1_3_2_1_47_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Indyk Piotr","year":"2003","unstructured":"Piotr Indyk. Better algorithms for high-dimensional proximity problems via asymmetric embeddings. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), 2003."},{"key":"e_1_3_2_1_48_1","first-page":"811","volume-title":"Proceedings of the 56th Annual ACM Symposium on Theory of Computing","author":"Jayaram Rajesh","year":"2024","unstructured":"Rajesh Jayaram, Erik Waingarten, and Tian Zhang. Data-dependent lsh for the earth mover\u2019s distance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 800\u2013811, 2024."},{"key":"e_1_3_2_1_49_1","volume-title":"37th International Symposium on Computational Geometry","author":"Kush Deepanshu","year":"2021","unstructured":"Deepanshu Kush, Aleksandar Nikolov, and Haohua Tang. Near neighbor search via efficient average distortion embeddings. In 37th International Symposium on Computational Geometry, 2021."},{"key":"e_1_3_2_1_50_1","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS)","author":"Khanna Sanjeev","year":"2025","unstructured":"Sanjeev Khanna, Ashwin Padaki, Krish Singal, and Erik Waingarten. A polynomial space lower bound for diameter estimation in dynamic streams. In Proceedings of the Symposium on Foundations of Computer Science (FOCS), 2025. arXiv preprint arXiv:2510.04918."},{"key":"e_1_3_2_1_51_1","first-page":"316","volume-title":"International Workshop on Approximation Algorithms for Combinatorial Optimization","author":"Gharan Shayan Oveis","unstructured":"Shayan Oveis Gharan and Luca Trevisan. A new regularity lemma and faster approximation algorithms for low threshold rank graphs. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 303\u2013316. Springer, 2013."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.07.006"},{"key":"e_1_3_2_1_53_1","first-page":"1268","volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing","author":"Rubinstein Aviad","unstructured":"Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1260\u20131268. ACM, 2018."},{"key":"e_1_3_2_1_54_1","first-page":"1408","volume-title":"Proceedings of the 2013 conference on Computer supported cooperative work","author":"Said Alan","year":"2013","unstructured":"Alan Said, Ben Fields, Brijnesh J Jain, and Sahin Albayrak. User-centric evaluation of a k-furthest neighbor collaborative filtering recommender algorithm. In Proceedings of the 2013 conference on Computer supported cooperative work, pages 1399\u20131408, 2013."},{"key":"e_1_3_2_1_55_1","first-page":"233","volume-title":"Proceedings of the Seventh ACM Symposium on Theory of Computing","author":"Shamos I.","year":"1975","unstructured":"I. Shamos. Geometric complexity. Proceedings of the Seventh ACM Symposium on Theory of Computing, pages 224\u2013233, 1975."},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.5555\/892057"},{"key":"e_1_3_2_1_57_1","first-page":"136","volume-title":"2009 24th Annual IEEE Conference on Computational Complexity","author":"Trevisan Luca","unstructured":"Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In 2009 24th Annual IEEE Conference on Computational Complexity, pages 126\u2013136. IEEE, 2009."},{"key":"e_1_3_2_1_58_1","volume-title":"Proceedings of ICM 2018","author":"Williams Virginia Vassilevska","year":"2018","unstructured":"Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of ICM 2018, 2018."},{"key":"e_1_3_2_1_59_1","first-page":"1877","volume-title":"Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms","author":"Williams Ryan","unstructured":"Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1867\u20131877. SIAM, 2014."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800856","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800856","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:15Z","timestamp":1781028315000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800856"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":59,"alternative-id":["10.1145\/3798129.3800856","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800856","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}