9 problems

Let $A$ be a $d$-by-$d$ matrix whose entries are chosen independently and uniformly from $\{ -1,1\}$. Random sign matrix inverse-norm conjecture. … for some absolute constant…

Let $\orig{A}$ be an arbitrary $d$-by-$d$ real matrix, and let $A$ be a matrix of independent Gaussian random variables centered at $\orig{A}$, each of variance $\sigma^2$. Gaussia…

Let $\widetilde{A}$ be an $n\times n$ matrix satisfying $\|\widetilde{A}\|_2\leq\sqrt{n}$, and let $A$ be a Gaussian perturbation of $\widetilde{A}$ with variance $\sigma^2\leq1$.…

Let $\widetilde{A}$ be an $n\times n$ matrix with $\|\widetilde{A}\|_2\leq 1$, and let $A$ be a Gaussian perturbation of $\widetilde{A}$ with variance $\sigma^2\leq1$. Let $U$ be t…

Let $A$ be a Gaussian perturbation of a square matrix $\widetilde{A}$, in the setting of the preceding smoothed condition-number analysis. Logarithmic-factor conjecture. The factor…

Let $\widetilde{A}$ be an arbitrary square matrix in $\mathbb{R}^{n\times n}$, and let $A$ be a Gaussian perturbation of $\widetilde{A}$ with variance $\sigma^2$. Smallest singular…

Smoothed hardness conjecture. Finding a Nash equilibrium remains hard even when small independent perturbations are applied to the entries of a bimatrix game; equivalently, the pro…

Let $A$ be an $n\times n$ symmetric random matrix whose independent upper-triangular entries have continuous distributions with densities bounded by $K$. For a deterministic symmet…

Let $A$ be an arbitrary $n \times n$ matrix, and let $M_n$ be a random $n \times n$ matrix. For an invertible matrix $M$, define its condition number by … and set…