References

Surveys

• Recent Progress on Rigidity: A Survey (C Ramya, 2020)
• Sasha Golovnev's course on Matrix Rigidity (2020)
• Emanuele Viola's blogpost on Matrix Rigidity (2016)
• Satya Lokam's Tutorial in Simons Institute (2014)
• Stasys Jukna and Igor Sergeev's survey (2013)
• Complexity Lower Bounds using Linear Algebra (Satya Lokam, 2009)
• Mahdi Cheraghchi's survey (2005)
• Bruno Codenotti's survey (2000)

Recent Papers

• Rigid Matrices From Rectangular PCPs Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal (2020)
• Efficient Construction of Rigid Matrices Using an NP Oracle Josh Alman and Lijie Chen (2019)
• Equivalence of Systematic Linear Data Structures and Matrix Rigidity Sivaramakrishnan Natarajan Ramamoorthy, Cyrus Rashtchian (2019)
• Static Data Structure Lower Bounds Imply Rigidity Zeev Dvir, Alexander Golovnev, Omri Weinstein (2018)
• Fourier and Circulant Matrices are Not Rigid Zeev Dvir, Allen Liu (2019)
• Matrix rigidity and the Croot-Lev-Pach lemma Zeev Dvir, Benjamin Edelman (2017)
• A generating matrix of a good code may have low rigidity A note written by Oded Goldreich on Zeev Dvir's proof.
• Probabilistic Rank and Matrix Rigidity Josh Alman, Ryan Williams (2016) Josh Alman's TCS+ Talk
• Matrix Rigidity of Random Toeplitz Matrices Oded Goldreich and Avishay Tal (2016)
• Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity Alex Samorodnitsky, Ilya Shkredov, and Sergey Yekhanin (2015)
• On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions Oded Goldreich and Avi Wigderson (2019)
• A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices Mrinal Kumar, Ben Lee Volk (2020)
• Lower Bounds for Matrix Factorization Mrinal Kumar, Ben Lee Volk (2019)
• Complexity of linear circuits and geometry Fulvio Gesmundo, Jonathan Hauenstein, Christian Ikenmeyer, JM Landsberg (2013)
• Using Elimination Theory to construct Rigid Matrices Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar, Jayalal Sarma M. N (2009)
• Matrix Rigidity from the Viewpoint of Parameterized Complexity Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi (2017)
• Bounded Matrix Rigidity and John's Theorem Cyrus Rashtchian (2016)
• Noisy Interpolation of Sparse Polynomials, and Applications Shubhangi Saraf ; Sergey Yekhanin (2011)
• Improved rank bounds for design matrices and a new proof of Kelly’s theorem Zeev Dvir, Shubhangi Saraf, Avi Wigderson (2012)
• Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff (2011)
• On matrix rigidity and locally self-correctable codes Zeev Dvir (2010)
• On Rigid Matrices and U-Polynomials Noga Alon and Gil Cohen (2012)
• On a special case of rigidity Rocco Servedio, Emanuele Viola (2012)
• Min-Rank Conjecture for Log-Depth Circuits Stasys Jukna, Georg Schnitger (2009)
• Shachar Lovett's Talk and article on log rank conjecture
• On a theorem of Razborov (Henning Wunderlich) 2012
• On a rank game Justin Yu (2019)