Matrix Rigidity and the Croot-Lev-Pach Lemma

by Zeev Dvir and Benjamin L. Edelman

Theory of Computing, Volume 15(8), pp. 1-7, 2019

Bibliography with links to cited articles

[1]   Josh Alman and Ryan Williams: Probabilistic rank and matrix rigidity. In Proc. 49th STOC, pp. 641–652. ACM Press, 2017. [doi:10.1145/3055399.3055484, arXiv:1611.05558]

[2]   Ernie Croot, Vsevolod F. Lev, and Péter Pál Pach: Progression-free sets in Z4n are exponentially small. Ann. of Math, 185(1):331–337, 2017. [doi:10.4007/annals.2017.185.1.7, arXiv:1605.01506]

[3]   Zeev Dvir and Allen Liu: Fourier and circulant matrices are not rigid. In Proc. 34th Conf. Comput. Complexity (CCC’19), pp. 17:1–17:23. Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.17]

[4]   Jordan S. Ellenberg and Dion Gijswijt: On large subsets of Fqn with no three-term arithmetic progression. Ann. of Math, 185(1):339–343, 2017. [doi:10.4007/annals.2017.185.1.8, arXiv:1605.09223]

[5]   Joel Friedman: A note on matrix rigidity. Combinatorica, 13(2):235–239, 1993. [doi:10.1007/BF01303207]

[6]   Wassily Hoeffding: Probability inequalities for sums of bounded random variables. J. Amer. Statistical Assoc., 58(301):13–30, 1963. [doi:10.1080/01621459.1963.10500830]

[7]   Satyanarayana V. Lokam: Complexity lower bounds using linear algebra. Found. Trends Theor. Comput. Sci., 4(1–2):1–155, 2009. [doi:10.1561/0400000011]

[8]   M. Amin Shokrollahi, Daniel A. Spielman, and Volker Stemann: A remark on matrix rigidity. Inform. Process. Lett., 64(6):283–285, 1997. [doi:10.1016/S0020-0190(97)00190-7]

[9]   Victor Shoup and Roman Smolensky: Lower bounds for polynomial evaluation and interpolation problems. Comput. Complexity, 6(4):301–311, 1996. Preliminary version in FOCS’91. [doi:10.1007/BF01270384]

[10]   Leslie G. Valiant: Graph-theoretic arguments in low-level complexity. In Proc. 6th Internat. Symp. Math. Found. Comput. Sci. (MFCS’77), pp. 162–176. Springer, 1977. [doi:10.1007/3-540-08353-7_135]