Fourier and Circulant Matrices are Not Rigid

by Zeev Dvir and Allen Liu

Theory of Computing, Volume 16(20), pp. 1-48, 2020

Bibliography with links to cited articles

[1]   Josh Alman and Lijie Chen: Efficient construction of rigid matrices using an NP oracle. In Proc. 60th FOCS, pp. 1034–1055. IEEE Comp. Soc., 2019. [doi:10.1109/FOCS.2019.00067]

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

[3]   Richard Arratia and Louis Gordon: Tutorial on large deviations for the binomial distribution. Bull. Mathematical Biology, 51(1):125–131, 1989. [doi:10.1007/BF02458840]

[4]   László Babai and Bohdan Kivva: Matrix rigidity: More conjectures refuted. In preparation.

[5]   Roger C. Baker and Glyn Harman: Shifted primes without large prime factors. Acta Arithmetica, 83(4):331–361, 1998. [doi:10.4064/aa-83-4-331-361]

[6]   Giuliana Davidoff, Peter Sarnak, and Alain Valette: Elementary Number Theory, Group Theory, and Ramanujan Graphs. Volume 55 of LMS Student Texts. Cambridge Univ. Press, 2003. [doi:10.1017/CBO9780511615825]

[7]   Zeev Dvir and Benjamin Edelman: Matrix rigidity and the Croot-Lev-Pach lemma. Theory of Computing, 15(8):1–7, 2019. [doi:10.4086/toc.2019.v015a008, arXiv:1708.01646]

[8]   Zeev Dvir and Allen Liu: Fourier and circulant matrices are not rigid. In 34th Computational Complexity Conference (CCC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.17]

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

[10]   Ferdinand Georg Frobenius: Über Gruppencharaktere. Sitzungsberichte der Preußischen Akademie der Wissenschaften zu Berlin, 39:985–1021, 1896.

[11]   Oded Goldreich and Avishay Tal: Matrix rigidity of random Toeplitz matrices. Comput. Complexity, 27(2):305–350, 2018. Preliminary version in STOC’16. [doi:10.1007/s00037-016-0144-9]

[12]   Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, and M. N. Jayalal Sarma: Using elimination theory to construct rigid matrices. Comput. Complexity, 23(4):531–563, 2014. [doi:10.1007/s00037-013-0061-0, arXiv:0910.5301]

[13]   Serge Lang: Algebra. Volume 211 of Grad. Texts in Math. Springer, 3rd edition, 1996.

[14]   Rudolf Lidl and Harald Niederreiter: Finite Fields. Encycl. Math. Appl. Cambridge Univ. Press, 2nd edition, 1996. [doi:10.1017/CBO9780511525926]

[15]   Satyanarayana V. Lokam: On the rigidity of Vandermonde matrices. Theoret. Comput. Sci., 237(1–2):477–483, 2000. [doi:10.1016/S0304-3975(00)00008-6]

[16]   Satyanarayana V. Lokam: Quadratic lower bounds on matrix rigidity. In Internat. Conf. on Theory and Appl. of Models of Computation (TAMC’06), pp. 295–307. Springer, 2006. [doi:10.1007/11750321_28]

[17]   Satyanarayana V. Lokam: Complexity lower bounds using linear algebra. Foundations and Trends in Theoretical Computer Science, 4(1–2):1–155, 2009. [doi:10.1561/0400000011]

[18]   Mohammad 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]

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