Fetching the paper…

Reading the bibliography…

2017

Matrix rigidity and the Croot-Lev-Pach lemma

Dvir, Zeev, Edelman, Benjamin

Original
PDF
Post on X

Understand

Matrix rigidity is a notion put forth by Valiant as a means for proving arithmetic circuit lower bounds.

A matrix is rigid if it is far, in Hamming distance, from any low rank matrix.
Despite decades of efforts, no explicit matrix rigid enough to carry out Valiant's plan has been found.
Recently, Alman and Williams showed, contrary to common belief, that the $2^n \times 2^n$ Hadamard matrix could not be used for Valiant's program as it is not sufficiently rigid.

Matrix rigidity and the Croot-Lev-Pach lemma · Around

Built on

L. Valiant. Graph-theoretic arguments in low-level complexity. Mathematical Foundations of Computer Science , pages 162-176, 1977
1977
Earlier work this paper cites.
Joel Friedman. A note on matrix rigidity. Combinatorica , 13(2):235–239, 1993
1993
Earlier work this paper cites.
M.A. Shokrollahi, D.A. Spielman, and V. Stemann. A remark on matrix rigidity. Information Processing Letters , 64(6):283 – 285, 1997
1997
Earlier work this paper cites.
S. V. Lokam. (2009). Complexity lower bounds using linear algebra. Foundations and Trends in Theoretical Computer Science , 4(1–2), pages 1-155, 2009
2009
Earlier work this paper cites.

Similar

O. Goldreich and A. Wigderson. ”On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions.” Electronic Colloquium on Computational Complexity , 43, pages 1-40, 2013
2013
Cited alongside, same era.
F. Rassoul-Agha and T. Seppäläinen. A Course on Large Deviations with an Introduction to Gibbs Measures . Graduate Studies in Mathematics, 162, American Mathematical Society, 2015
2015
Cited alongside, same era.
O. Goldreich and A. Tal. Matrix Rigidity of Random Toeplitz Matrices. Computational Complexity , pages 1-46, 2016
2016
Cited alongside, same era.

Then

J. Alman and R. Williams. Probabilistic Rank and Matrix Rigidity. arXiv:1611.05558, to appear in 49th ACM Symposium on Theory of Computing , 2017
Original
2017
Closest in time.
E. Croot, V. Lev, and P. Pach. Progression-free sets in ℤ 4 n \mathbb{Z}_{4}^{n} are exponentially small. Annals of Mathematics , 185(1), pages 331-337, 2017
2017
Closest in time.
J. S. Ellenberg and D. Gijswijt. On large subsets of 𝔽 q n {\mathbb{F}}_{q}^{n} with no three-term arithmetic progression. Annals of Mathematics , 185(1), pages 339-343, 2017
2017
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…