[1]   Scott Aaronson and Avi Wigderson: Algebrization: A new barrier in complexity theory. ACM Trans. Comput. Theory, 1(1):2:1–2:54, 2009. Preliminary version in STOC’08. [doi:10.1145/1490270.1490272]

[2]   Amir Abboud and Arturs Backurs: Towards hardness of approximation for polynomial time problems. In Proc. 8th Symp. Innovations in Theoretical Computer Science (ITCS’17), pp. 11:1–11:26. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.11]

[3]   Amir Abboud and Søren Dahlgaard: Popular conjectures as a barrier for dynamic planar graph algorithms. In Proc. 57th FOCS, pp. 477–486. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.58, arXiv:1605.03797]

[4]   Amir Abboud and Aviad Rubinstein: Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds. In Proc. 9th Symp. Innovations in Theoretical Computer Science (ITCS’18), pp. 35:1–35:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ITCS.2018.35]

[5]   Amir Abboud, Aviad Rubinstein, and R. Ryan Williams: Distributed PCP theorems for hardness of approximation in P. In Proc. 58th FOCS, pp. 25–36. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.12, arXiv:1706.06407]

[6]   Amir Abboud, Richard R. Ryan Williams, and Huacheng Yu: More applications of the polynomial method to algorithm design. In Proc. 26th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’15), pp. 218–230. ACM Press, 2015. [doi:10.1137/1.9781611973730.17]

[7]   Amir Abboud and Virginia Vassilevska Williams: Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th FOCS, pp. 434–443. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.53, arXiv:1402.0054]

[8]   Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann: Consequences of faster alignment of sequences. In Proc. 41st Internat. Colloq. on Automata, Languages and Programming (ICALP’14), pp. 39–51. Springer, 2014. [doi:10.1007/978-3-662-43948-7_4]

[9]   Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu: Matching triangles and basing hardness on an extremely popular conjecture. SIAM J. Comput., 47(3):1098–1122, 2018. Preliminary version in STOC’15. [doi:10.1137/15M1050987]

[10]   Pankaj K. Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl: Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput. Geom., 6(3):407–422, 1991. Preliminary version in SoCG’90. [doi:10.1007/BF02574698]

[11]   Thomas Dybdahl Ahle, Rasmus Pagh, Ilya P. Razenshteyn, and Francesco Silvestri: On the complexity of inner product similarity join. In Proc. 35th ACM Symp. Principles of Database Sys. (PODS’16), pp. 151–164. ACM Press, 2016. [doi:10.1145/2902251.2902285, arXiv:1510.02824]

[12]   Josh Alman: An illuminating algorithm for the light bulb problem. In 2nd Symp. on Simplicity in Algorithms (SOSA’19), pp. 2:1–2:11, 2019. [doi:10.4230/OASIcs.SOSA.2019.2, arXiv:1810.06740]

[13]   Josh Alman, Timothy M. Chan, and R. Ryan Williams: Polynomial representations of threshold functions and algorithmic applications. In Proc. 57th FOCS, pp. 467–476. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.57, arXiv:1608.04355]

[14]   Josh Alman and R. Ryan Williams: Probabilistic polynomials and Hamming nearest neighbors. In Proc. 56th FOCS, pp. 136–150. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.18, arXiv:1507.05106]

[15]   Alexandr Andoni and Piotr Indyk: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. Comm. ACM, 51(1):117–122, 2008. Conference version in FOCS’06. [doi:10.1145/1327452.1327494]

[16]   Alexandr Andoni, Piotr Indyk, Thijs Laarhoven, Ilya P. Razenshteyn, and Ludwig Schmidt: Practical and optimal LSH for angular distance. In Adv. in Neural Inform. Proc. Systems (NIPS’15), pp. 1225–1233. MIT Press, 2015. NIPS. [arXiv:1509.02897]

[17]   Alexandr Andoni, Piotr Indyk, Huy Lê Nguyên, and Ilya P. Razenshteyn: Beyond locality-sensitive hashing. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1018–1028. ACM Press, 2014. [doi:10.1137/1.9781611973402.76, arXiv:1306.1547]

[18]   Alexandr Andoni and Ilya P. Razenshteyn: Optimal data-dependent hashing for approximate near neighbors. In Proc. 47th STOC, pp. 793–801. ACM Press, 2015. [doi:10.1145/2746539.2746553, arXiv:1501.01062]

[19]   Tom M. Apostol: Introduction to Analytic Number Theory. Springer, 2013. [doi:10.1007/978-1-4757-5579-4]

[20]   Sanjeev Arora and Boaz Barak: Computational Complexity – A Modern Approach. Cambridge Univ. Press, 2009.

[21]   Arturs Backurs and Piotr Indyk: Which regular expression patterns are hard to match? In Proc. 57th FOCS, pp. 457–466. IEEE Comp. Soc., 2016. [doi:10.1109/FOCS.2016.56, arXiv:1511.07070]

[22]   Arturs Backurs and Piotr Indyk: Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). SIAM J. Comput., 47(3):1087–1097, 2018. Preliminary version in STOC’15. [doi:10.1137/15M1053128, arXiv:1412.0348]

[23]   Jon Louis Bentley and Michael Ian Shamos: Divide-and-conquer in multidimensional space. In Proc. 8th STOC, pp. 220–230. ACM Press, 1976. [doi:10.1145/800113.803652]

[24]   Karl Bringmann: Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th FOCS, pp. 661–670. IEEE Comp. Soc., 2014. [doi:10.1109/FOCS.2014.76, arXiv:1404.1448]

[25]   Karl Bringmann, Allan Grønlund, and Kasper Green Larsen: A dichotomy for regular expression membership testing. In Proc. 58th FOCS, pp. 307–318. IEEE Comp. Soc., 2017. [doi:10.1109/FOCS.2017.36, arXiv:1611.00918]

[26]   Karl Bringmann and Marvin Künnemann: Multivariate fine-grained complexity of longest common subsequence. In Proc. 29th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’18), pp. 1216–1235. ACM Press, 2018. [doi:10.1137/1.9781611975031.79, arXiv:1803.00938]

[27]   Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka: Bounds for small-error and zero-error quantum algorithms. In Proc. 40th FOCS, pp. 358–368. IEEE Comp. Soc., 1999. [doi:10.1109/SFFCS.1999.814607, arXiv:cs/9904019]

[28]   Harry Buhrman, Richard Cleve, and Avi Wigderson: Quantum vs. classical communication and computation. In Proc. 30th STOC, pp. 63–68. ACM Press, 1998. [doi:10.1145/276698.276713, arXiv:quant-ph/9802040]

[29]   Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi: The complexity of satisfiability of small depth circuits. In 4th Internat. Workshop on Parameterized and Exact Computation (IWPEC’09), pp. 75–85. Springer, 2009. [doi:10.1007/978-3-642-11269-0_6]

[30]   Timothy M. Chan: A (slightly) faster algorithm for Klee’s measure problem. Comput. Geom., 43(3):243–250, 2010. Preliminary version in SoCG’08. [doi:10.1016/j.comgeo.2009.01.007]

[31]   Lijie Chen, Shafi Goldwasser, Kaifeng Lyu, Guy N. Rothblum, and Aviad Rubinstein: Fine-grained complexity meets IP = PSPACE. In Proc. 30th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’19), pp. 1–20. ACM Press, 2019. [doi:10.1137/1.9781611975482.1, arXiv:1805.02351]

[32]   Lijie Chen and R. Ryan Williams: An equivalence class for orthogonal vectors. In Proc. 30th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’19), pp. 21–40. ACM Press, 2019. [doi:10.1137/1.9781611975482.2, arXiv:1811.12017]

[33]   Tobias Christiani: A framework for similarity search with space-time tradeoffs using locality-sensitive filtering. In Proc. 28th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’17), pp. 31–46. ACM Press, 2017. [doi:10.1137/1.9781611974782.3, arXiv:1605.02687]

[34]   Tobias Christiani and Rasmus Pagh: Set similarity search beyond minhash. In Proc. 49th STOC, pp. 1094–1107. ACM Press, 2017. [doi:10.1145/3055399.3055443, arXiv:1612.07710]

[35]   Don Coppersmith: Rapid multiplication of rectangular matrices. SIAM J. Comput., 11(3):467–471, 1982. [doi:10.1137/0211037]

[36]   Svyatoslav Covanov and Emmanuel Thomé: Fast integer multiplication using generalized Fermat primes. Math. Comput., 88(317):1449–1477, 2019. [doi:10.1090/mcom/3367]

[37]   Roee David, Karthik C. S., and Bundit Laekhanukit: On the complexity of closest pair via polar-pair of point-sets. SIAM J. Discrete Math., 33(1):509–527, 2019. Preliminary version in SoCG’18. [doi:10.1137/17M1128733, arXiv:1608.03245]

[38]   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. [doi:10.1006/jagm.1997.0873]

[39]   Martin Fürer: Faster integer multiplication. SIAM J. Comput., 39(3):979–1005, 2009. Preliminary version in STOC’07. [doi:10.1137/070711761]

[40]   Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and R. Ryan Williams: Completeness for first-order properties on sparse structures with algorithmic applications. ACM Trans. Algorithms, 15(3):23:1–23:35, 2018. Preliminary version in SODA’17. [doi:10.1145/3196275]

[41]   Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat: Conditional lower bounds for space/time tradeoffs. In Proc. 15th Internat. Workshop on Algorithms and Data Structures (WADS’17), pp. 421–436. Springer, 2017. [doi:10.1007/978-3-319-62127-2_36, arXiv:1706.05847]

[42]   Lov K. Grover: A fast quantum mechanical algorithm for database search. In Proc. 28th STOC, pp. 212–219. ACM Press, 1996. [doi:10.1145/237814.237866, arXiv:quant-ph/9605043]

[43]   Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani: Approximate nearest neighbors: Towards removing the curse of dimensionality. Theory of Computing, 8(14):321–350, 2012. Preliminary versions in STOC’98 and FOCS’01. [doi:10.4086/toc.2012.v008a014]

[44]   David Harvey, Joris van der Hoeven, and Grégoire Lecerf: Even faster integer multiplication. J. Complexity, 36(C):1–30, 2016. [doi:10.1016/j.jco.2016.03.001, arXiv:1407.3360]

[45]   Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak: Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. 47th STOC, pp. 21–30. ACM Press, 2015. [doi:10.1145/2746539.2746609, arXiv:1511.06773]

[46]   Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams: Conditional hardness for sensitivity problems. In Proc. 8th Symp. Innovations in Theoretical Computer Science (ITCS’17), pp. 26:1–26:31. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2017. [doi:10.4230/LIPIcs.ITCS.2017.26, arXiv:1703.01638]

[47]   Russell Impagliazzo and Ramamohan Paturi: On the complexity of k-SAT. J. Comput. System Sci., 62(2):367–375, 2001. Preliminary version in CCC’99. [doi:10.1006/jcss.2000.1727]

[48]   Piotr Indyk and Rajeev Motwani: Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proc. 30th STOC, pp. 604–613. ACM Press, 1998. [doi:10.1145/276698.276876]

[49]   Stasys Jukna: Boolean Function Complexity: Advances and Frontiers. Volume 27. Springer, 2012. [doi:10.1007/978-3-642-24508-4]

[50]   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. Preliminary version in SODA’16. [doi:10.1145/3174804, arXiv:1510.03895]

[51]   Karthik C. S., Bundit Laekhanukit, and Pasin Manurangsi: On the parameterized complexity of approximating dominating set. J. ACM, 66(5):33:1–33:38, 2019. Preliminary version in STOC’18. [doi:10.1145/3325116, arXiv:1711.11029]

[52]   Karthik C. S. and Pasin Manurangsi: On closest pair in Euclidean metric: Monochromatic is as hard as bichromatic. Combinatorica, 2020. Preliminary version in ITCS’19. [doi:10.1007/s00493-019-4113-1, arXiv:1812.00901]

[53]   Samir Khuller and Yossi Matias: A simple randomized sieve algorithm for the closest-pair problem. Inform. and Comput., 118(1):34–37, 1995. [doi:10.1006/inco.1995.1049]

[54]   Hartmut Klauck: Rectangle size bounds and threshold covers in communication complexity. In Proc. 18th Conf. Computational Complexity (CCC’03), pp. 118–134. IEEE Comp. Soc., 2003. [doi:10.1109/CCC.2003.1214415, arXiv:cs/0208006]

[55]   Tsvi Kopelowitz, Seth Pettie, and Ely Porat: Higher lower bounds from the 3SUM conjecture. In Proc. 27th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’16), pp. 1272–1287. ACM Press, 2016. [doi:10.1137/1.9781611974331.ch89, arXiv:1407.6756]

[56]   Robert Krauthgamer and Ohad Trabelsi: Conditional lower bounds for all-pairs max-flow. ACM Trans. Algorithms, 14(4):42:1–42:15, 2018. Preliminary version in ICALP’17. [doi:10.1145/3212510, arXiv:1702.05805]

[57]   François Le Gall and Florent Urrutia: Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor. In Proc. 29th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’18), pp. 1029–1046. ACM Press, 2018. [doi:10.1137/1.9781611975031.67, arXiv:1708.05622]

[58]   Jiří Matoušek: Efficient partition trees. Discrete Comput. Geom., 8(3):315–334, 1992. Preliminary version in SoCG’91. [doi:10.1007/BF02293051]

[59]   Jiří Matoušek: Range searching with efficient hierarchical cuttings. Discrete Comput. Geom., 10(2):157–182, 1993. Preliminary version in SoCG’92. [doi:10.1007/BF02573972]

[60]   Behnam Neyshabur and Nathan Srebro: On symmetric and asymmetric LSHs for inner product search. In Proc. 32nd Int. Conf. on Machine Learning (ICML’15), pp. 1926–1934, 2015. MLR Press. [arXiv:1410.5518]

[61]   Mihai Pătraşcu: Towards polynomial lower bounds for dynamic problems. In Proc. 42nd STOC, pp. 603–610. ACM Press, 2010. [doi:10.1145/1806689.1806772]

[62]   Mihai Pătraşcu and R. Ryan Williams: On the possibility of faster SAT algorithms. In Proc. 21st Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’10), pp. 1065–1075. ACM Press, 2010. [doi:10.1137/1.9781611973075.86]

[63]   Ramamohan Paturi and Janos Simon: Probabilistic communication complexity. J. Comput. System Sci., 33(1):106–123, 1986. Preliminary version in FOCS’84. [doi:10.1016/0022-0000(86)90046-2]

[64]   Ali Rahimi and Benjamin Recht: Random features for large-scale kernel machines. In Adv. in Neural Inform. Proc. Systems (NIPS’07), pp. 1177–1184. MIT Press, 2007. NIPS.

[65]   Parikshit Ram and Alexander G. Gray: Maximum inner-product search using cone trees. In Proc. 18th Internat. Conf. on Knowledge Discovery and Data Mining (KDD’12), pp. 931–939. ACM Press, 2012. [doi:10.1145/2339530.2339677]

[66]   Liam Roditty and Virginia Vassilevska Williams: Fast approximation algorithms for the diameter and radius of sparse graphs. In Proc. 45th STOC, pp. 515–524. ACM Press, 2013. [doi:10.1145/2488608.2488673]

[67]   Aviad Rubinstein: Hardness of approximate nearest neighbor search. In Proc. 50th STOC, pp. 1260–1268. ACM Press, 2018. [doi:10.1145/3188745.3188916, arXiv:1803.00904]

[68]   Anshumali Shrivastava and Ping Li: Asymmetric LSH (ALSH) for sublinear time maximum inner product search (MIPS). In Adv. in Neural Inform. Proc. Systems (NIPS’14), pp. 2321–2329. MIT Press, 2014. NIPS. [arXiv:1405.5869]

[69]   Anshumali Shrivastava and Ping Li: Asymmetric minwise hashing for indexing binary inner products and set containment. In Proc. 24th Int. World Wide Web Conf. (WWW’15), pp. 981–991, 2015. [doi:10.1145/2736277.2741285]

[70]   Christina Teflioudi and Rainer Gemulla: Exact and approximate maximum inner product search with LEMP. ACM Trans. Database Syst., 42(1):5:1–5:49, 2016. [doi:10.1145/2996452]

[71]   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. Preliminary version in FOCS’12. [doi:10.1145/2728167]

[72]   Virginia Vassilevska Williams: On some fine-grained questions in algorithms and complexity. In Proc. Internat. Congr. of Mathematicians (ICM 2018), volume 4, pp. 3447–3487. World Scientific, 2019. [doi:10.1142/9789813272880_0188]

[73]   R. Ryan Williams: A new algorithm for optimal 2-constraint satisfaction and its implications. Theoret. Comput. Sci., 348(2–3):357–365, 2005. Preliminary version in ICALP’04. [doi:10.1016/j.tcs.2005.09.023]

[74]   R. Ryan Williams: Faster all-pairs shortest paths via circuit complexity. SIAM J. Comput., 47(5):1965–1985, 2018. Preliminary version in STOC’14. [doi:10.1137/15M1024524, arXiv:1312.6680]

[75]   R. Ryan Williams: On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity. In Proc. 29th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’18), pp. 1207–1215. ACM Press, 2018. [doi:10.1137/1.9781611975031.78, arXiv:1709.05282]

[76]   R. Ryan Williams and Huacheng Yu: Finding orthogonal vectors in discrete structures. In Proc. 25th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’14), pp. 1867–1877. ACM Press, 2014. [doi:10.1137/1.9781611973402.135]

[77]   Ronald de Wolf: A note on quantum algorithms and the minimal degree of ϵ-error polynomials for symmetric functions. Quantum Info. Comput., 8(10):943–950, 2008. [doi:10.26421/QIC8.10, arXiv:0802.1816]

[78]   Andrew Chi-Chih Yao: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput., 11(4):721–736, 1982. [doi:10.1137/0211059]