  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
\times 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^{\epsilon n}$ entries in each row and make the rank drop below
$2^{n(1-\Omega(\epsilon^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 $n
\times n$ Boolean matrices which maintain rank at least $2^{(\log
n)^{1-\delta}}$ after $n^2/2^{(\log n)^{\delta/2}}$ modified entries would
yield a function lacking sub-quadratic-size $AC^0$ circuits with two layers of
arbitrary linear threshold gates. We also prove that explicit 0/1 matrices over
$\mathbb{R}$ 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 $THR\circ THR$.
