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

matrix rigidityprobabilistic rankthreshold circuitWalsh-Hadamard transform

Mathematics Subject Classification ID

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

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

(40)

• Improved lower bounds on the rigidity of Hadamard matrices
• Matrix rigidity of random Toeplitz matrices
• Some structural properties of low-rank matrices related to computational complexity
• Lower bounds for matrix factorization
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Matrix and tensor rigidity and L_p-approximation
• Predicate encryption from bilinear maps and one-sided probabilistic rank
• On the complexity of matrix rank and rigidity
• On the Complexity of Matrix Rank and Rigidity
• On a theorem of Razborov
• New applications of the polynomial method: the cap set conjecture and beyond
• scientific article; zbMATH DE number 1405679 (Why is no real title available?)
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• A short list of equalities induces large sign-rank
• Classical algorithms from quantum and Arthur-Merlin communication protocols
• On the inner product predicate and a generalization of matching vector families
• Fourier and circulant matrices are not rigid
• Lower bounds for matrix factorization
• scientific article; zbMATH DE number 7561745 (Why is no real title available?)
• Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
• Matrix rigidity and the Croot-Lev-Pach lemma
• Matrix rigidity of random toeplitz matrices
• Fourier and circulant matrices are not rigid
• Efficient Construction of Rigid Matrices Using an NP Oracle
• Theory and Applications of Models of Computation
• Arithmetic circuits, structured matrices and (not so) deep learning
• On matrix rigidity and locally self-correctable codes
• 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
• Limits of preprocessing
• Widths and rigidity
• Nondeterministic and randomized Boolean hierarchies in communication complexity
• Efficient construction of rigid matrices using an NP oracle
• Widths and rigidity of unconditional sets and random vectors
• Fast, algebraic multivariate multipoint evaluation in small characteristic and applications
• Block rigidity: strong multiplayer parallel repetition implies super-linear lower bounds for Turing machines
• On approximate symmetric polynomials and tightness of homogenization results
• \#SAT-algorithms for classes of threshold circuits based on probabilistic rank
• Kronecker products, low-depth circuits, and matrix rigidity

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)