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]