Optimal and algorithmic norm regularization of random matrices

Let $A$ be an $ntimes n$ random matrix whose entries are i.i.d. with mean $0$ and variance $1$. We present a deterministic polynomial time algorithm which, with probability at least $1-2exp(-Omega(epsilon n))$ in the choice of $A$, finds an $epsilon n times epsilon n$ sub-matrix such that zeroing it out results in $widetilde{A}$ with [|widetilde{A}| = Oleft(sqrt{n/epsilon}right).] Our result is optimal up to a constant factor and improves previous results of Rebrova and Vershynin, and Rebrova. We also prove an analogous result for $A$ a symmetric $ntimes n$ random matrix whose upper-diagonal entries are i.i.d. with mean $0$ and variance $1$.