[1]   Nguyen Quang A, László Gyrfi, and James L. Massey: Constructions of binary constant-weight cyclic codes and cyclically permutable codes. IEEE Trans. Inform. Theory, 38(3):940–949, 1992. [doi:10.1109/18.135636]

[2]   Karl R. Abrahamson: Generalized string matching. SIAM J. Comput., 16(6):1039–1051, 1987. [doi:10.1137/0216067]

[3]   Amihood Amir, Moshe Lewenstein, and Ely Porat: Faster algorithms for string matching with k mismatches. J. Algorithms, 50(2):257–275, 2004. Preliminary version in SODA’00. [doi:10.1016/S0196-6774(03)00097-X]

[4]   Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf: Better gap-Hamming lower bounds via better round elimination. In Proc. 14th Internat. Workshop on Randomization and Computation (RANDOM’10), pp. 476–489, 2010. [doi:10.1007/978-3-642-15369-3_36, arXiv:0912.5276]

[5]   Amit Chakrabarti and Oded Regev: An optimal lower bound on the communication complexity of gap-Hamming-distance. SIAM J. Comput., 41(5):1299–1317, 2012. Preliminary version in STOC’11. [doi:10.1137/120861072]

[6]   Raphaël Clifford, Klim Efremenko, Benny Porat, and Ely Porat: A black box for online approximate pattern matching. Inform. and Comput., 209(4):731–736, 2011. Preliminary version in CPM’08. [doi:10.1016/j.ic.2010.12.007]

[7]   Raphaël Clifford and Markus Jalsenius: Lower bounds for online integer multiplication and convolution in the cell-probe model. In Proc. 38th Internat. Colloq. on Automata, Languages and Programming (ICALP’11), pp. 593–604. Springer, 2011. [doi:10.1007/978-3-642-22006-7_50, arXiv:1101.0768]

[8]   Raphaël Clifford, Markus Jalsenius, and Benjamin Sach: Tight cell-probe bounds for online Hamming distance computation. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’13), pp. 664–674. ACM Press, 2013. [doi:10.1137/1.9781611973105.48, arXiv:1207.1885]

[9]   Raphaël Clifford and Benjamin Sach: Pattern matching in pseudo real-time. J. Discrete Algorithms, 9(1):67–81, 2011. Preliminary version in CPM’10. [doi:10.1016/j.jda.2010.09.005]

[10]   Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan: Comparing data streams using Hamming norms (how to zero in). IEEE Trans. on Knowl. and Data Eng., 15(3):529–540, 2003. Preliminary version in VLDB’02. [doi:10.1109/TKDE.2003.1198388]

[11]   David E. Daykin: Distribution of bordered persymmetric matrices in a finite field. J. reine angew. Math., 203:47–54, 1960. [doi:10.1515/crll.1960.203.47]

[12]   Michael J. Fischer and Larry J. Stockmeyer: Fast on-line integer multiplication. J. Comput. System Sci., pp. 317–331, 1974. Preliminary version in STOC’73. [doi:10.1016/S0022-0000(74)80047-4]

[13]   Michael L. Fredman: Observations on the complexity of generating quasi-Gray codes. SIAM J. Comput., 7(2):134–146, 1978. [doi:10.1137/0207012]

[14]   Michael L. Fredman and Mike E. Saks: The cell probe complexity of dynamic data structures. In Proc. 21st STOC, pp. 345–354, 1989. [doi:10.1145/73007.73040]

[15]   Zvi Galil: String matching in real time. J. ACM, 28(1):134–149, 1981. [doi:10.1145/322234.322244]

[16]   Torben Hagerup: Sorting and searching on the word RAM. In Proc. 15th Symp. Theoretical Aspects of Comp. Sci. (STACS’98), pp. 366–398, 1998. [doi:10.1007/BFb0028575]

[17]   Wei Huang, Yaoyun Shi, Shengyu Zhang, and Yufan Zhu: The communication complexity of the Hamming distance problem. Inform. Process. Lett., 99(4):149–153, 2006. [doi:10.1016/j.ipl.2006.01.014]

[18]   Piotr Indyk: Faster algorithms for string matching problems: Matching the convolution bound. In Proc. 39th FOCS, pp. 166–173, 1998. [doi:10.1109/SFCS.1998.743440]

[19]   T. S. Jayram, Ravi Kumar, and D. Sivakumar: The one-way communication complexity of Hamming distance. Theory of Computing, 4(6):129–135, 2008. [doi:10.4086/toc.2008.v004a006]

[20]   Erich Kaltofen and Austin A. Lobo: On rank properties of Toeplitz matrices over finite fields. In Proc. International Symp. on Symbolic and Algebraic Computation (ISSAC’96), pp. 241–249, 1996. [doi:10.1145/236869.237081]

[21]   Howard J. Karloff: Fast algorithms for approximately counting mismatches. Inform. Process. Lett., 48(2):53–60, 1993. [doi:10.1016/0020-0190(93)90177-B]

[22]   S. Rao Kosaraju: Efficient string matching. Manuscript, 1987.

[23]   Gad M. Landau and Uzi Vishkin: Efficient string matching with k mismatches. Theoret. Comput. Sci., 43:239–249, 1986. [doi:10.1016/0304-3975(86)90178-7]

[24]   Kasper Green Larsen: The cell probe complexity of dynamic range counting. In Proc. 44th STOC, pp. 85–94, 2012. [doi:10.1145/2213977.2213987, arXiv:1105.5933]

[25]   Kasper Green Larsen, Omri Weinstein, and Huacheng Yu: Crossing the logarithmic barrier for dynamic Boolean data structure lower bounds. In Proc. 50th STOC, 2017. [doi:10.1145/3188745.3188790, arXiv:1703.03575]

[26]   Ohad Lipsky and Ely Porat: L₁ pattern matching lower bound. Inform. Process. Lett., 105(4):141–143, 2008. Preliminary version in SPIRE’05. [doi:10.1016/j.ipl.2007.08.011]

[27]   Marvin Minsky and Seymour Papert: Perceptrons: An Introduction to Computational Geometry. MIT Press, 1969.

[28]   Jacques Morgenstern: Note on a lower bound on the linear complexity of the fast Fourier transform. J. ACM, 20(2):305–306, 1973. [doi:10.1145/321752.321761]

[29]   Victor Ya. Pan: The trade-off between the additive complexity and the asynchronicity of linear and bilinear algorithms. Inform. Process. Lett., 22(1–2):11–14, 1986. [doi:10.1016/0020-0190(86)90035-9]

[30]   Christos H. Papadimitriou: Optimality of the Fast Fourier Transform. J. ACM, 26(1):95–102, 1979. [doi:10.1145/322108.322118]

[31]   Mike S. Paterson, Michael J. Fischer, and Albert R. Meyer: An improved overlap argument for on-line multiplication. In SIAM-AMS Proceedings, volume 7, pp. 97–111. Amer. Math. Soc., 1974.

[32]   Mihai Pǎtraşcu: Lower bound techniques for data structures. Ph. D. thesis, MIT, 2008. ACM DL.

[33]   Mihai Pǎtraşcu and Erik D. Demaine: Tight bounds for the partial-sums problem. In Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’04), pp. 20–29. ACM Press, 2004. ACM DL.

[34]   Mihai Pătraşcu and Erik D. Demaine: Logarithmic lower bounds in the cell-probe model. SIAM J. Comput., 35(4):932–963, 2006. Preliminary versions in [33] and STOC’04. [doi:10.1137/S0097539705447256, arXiv:cs/0502041]

[35]   David Woodruff: Optimal space lower bounds for all frequency moments. In Proc. 15th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’04), pp. 167–175. ACM Press, 2004. ACM DL.

[36]   Andrew Chi-Chih Yao: Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th FOCS, pp. 222–227, 1977. Preliminary version in FOCS’78. [doi:10.1109/SFCS.1977.24]

[37]   Andrew Chi-Chih Yao: Should tables be sorted? J. ACM, 28(3):615–628, 1981. [doi:10.1145/322261.322274]