Probabilistic rank and matrix rigidity

DOI10.1145/3055399.3055484zbMATH Open1369.68212arXiv1611.05558OpenAlexW2553219432MaRDI QIDQ4978010FDOQ4978010

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)

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$.

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

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

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)

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
• Title not available (Why is that?)
• 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
• Matrix and tensor rigidity and \(L_p\)-approximation
• On matrix rigidity and locally self-correctable codes
• Uniqueness of Nonnegative Matrix Factorizations by Rigidity Theory
• On the complexity of matrix rank and rigidity
• 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
• Matrix rigidity of random toeplitz matrices
• On the inner product predicate and a generalization of matching vector families
• Algorithms for NP-Hard Problems via Rank-Related Parameters of Matrices
• Predicate encryption from bilinear maps and one-sided probabilistic rank
• On a theorem of Razborov
• 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
• Title not available (Why is that?)
• Matrix rigidity of random Toeplitz matrices
• New applications of the polynomial method: the cap set conjecture and beyond
• Title not available (Why is that?)

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)