Probabilistic rank and matrix rigidity

DOI10.1145/3055399.3055484MaRDI QIDQ4978010zbMATH OpenOpenAlexFDO

Authors Josh Alman, Ryan Williams

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1611.05558

zbMATH Keywords

Walsh-Hadamard transformmatrix rigiditythreshold circuitprobabilistic rank

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Boolean and Hadamard matrices (15B34) Vector spaces, linear dependence, rank, lineability (15A03) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: We consider a notion of probabilistic rank and probabilistic sign-rank of a matrix, which measures the extent to which a matrix can be probabilistically represented by low-rank matrices. We demonstrate several connections with matrix rigidity, communication complexity, and circuit lower bounds, including: The Walsh-Hadamard Transform is Not Very Rigid. We give surprising upper bounds on the rigidity of a family of matrices whose rigidity has been extensively studied, and was conjectured to be highly rigid. For the $2^{n}imes{2}^n$ Walsh-Hadamard transform $H_n$ (a.k.a. Sylvester matrices, or the communication matrix of Inner Product mod 2), we show how to modify only $2^{epsilonn}$ entries in each row and make the rank drop below $2^{n(1-Omega(epsilo{n}^2/log(1/epsilon)))}$, for all $epsilon>0$, over any field. That is, it is not possible to prove arithmetic circuit lower bounds on Hadamard matrices, via L. Valiant's matrix rigidity approach. We also show non-trivial rigidity upper bounds for $H_n$ with smaller target rank. Matrix Rigidity and Threshold Circuit Lower Bounds. We give new consequences of rigid matrices for Boolean circuit complexity. We show that explicit $nimesn$ Boolean matrices which maintain rank at least $2^{(logn{)}^{1-delta}}$ after $n^2/2^{(logn{)}^{delta/2}}$ modified entries would yield a function lacking sub-quadratic-size $A{C}^0$ circuits with two layers of arbitrary linear threshold gates. We also prove that explicit 0/1 matrices over $mathbbR$ which are modestly more rigid than the best known rigidity lower bounds for sign-rank would imply strong lower bounds for the infamously difficult class $THRcircTHR$.

Recommendations

• On the Complexity of Matrix Rank and Rigidity
• On the complexity of matrix rank and rigidity
• scientific article; zbMATH DE number 1436005
• Matrix rigidity of random Toeplitz matrices
• Matrix rigidity of random toeplitz matrices
• Resilience of the rank of random matrices
• The rank of sparse random matrices
• The rank of sparse random matrices
• Rank deficiency of random matrices

Cited in

(30)

• Fourier and circulant matrices are not rigid
• Lower bounds for matrix factorization
• Lower bounds for matrix factorization
• Fourier and circulant matrices are not rigid
• Matrix rigidity and the Croot-Lev-Pach lemma
• Limits of preprocessing
• scientific article; zbMATH DE number 7559066 (Why is no real title available?)
• Arithmetic circuits, structured matrices and (not so) deep learning
• Efficient Construction of Rigid Matrices Using an NP Oracle
• A short list of equalities induces large sign-rank
• On matrix rigidity and locally self-correctable codes
• Matrix and tensor rigidity and \(L_p\)-approximation
• On the complexity of matrix rank and rigidity
• Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
• Theory and Applications of Models of Computation
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• On the Complexity of Matrix Rank and Rigidity
• Widths and rigidity
• On the inner product predicate and a generalization of matching vector families
• Matrix rigidity of random toeplitz matrices
• On a theorem of Razborov
• Predicate encryption from bilinear maps and one-sided probabilistic rank
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• Rigid matrices from rectangular PCPs
• Faster Walsh-Hadamard and discrete Fourier transforms from matrix non-rigidity
• Range avoidance, remote point, and hard partial truth table via satisfying-pairs algorithms
• scientific article; zbMATH DE number 1405679 (Why is no real title available?)
• Matrix rigidity of random Toeplitz matrices
• New applications of the polynomial method: the cap set conjecture and beyond
• scientific article; zbMATH DE number 7561745 (Why is no real title available?)

This page was built for publication: Probabilistic rank and matrix rigidity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4978010)