  We initiate the study of the algorithmic problem of certifying lower bounds
on the discrepancy of random matrices: given an input matrix $A \in
\mathbb{R}^{m \times n}$, output a value that is a lower bound on
$\mathsf{disc}(A) = \min_{x \in \{\pm 1\}^n} ||Ax||_\infty$ for every $A$, but
is close to the typical value of $\mathsf{disc}(A)$ with high probability over
the choice of a random $A$. This problem is important because of its
connections to conjecturally-hard average-case problems such as
negatively-spiked PCA, the number-balancing problem and refuting random
constraint satisfaction problems. We give the first polynomial-time algorithms
with non-trivial guarantees for two main settings. First, when the entries of
$A$ are i.i.d. standard Gaussians, it is known that $\mathsf{disc} (A) = \Theta
(\sqrt{n}2^{-n/m})$ with high probability. Our algorithm certifies that
$\mathsf{disc}(A) \geq \exp(- O(n^2/m))$ with high probability. As an
application, this formally refutes a conjecture of Bandeira, Kunisky, and Wein
on the computational hardness of the detection problem in the negatively-spiked
Wishart model. Second, we consider the integer partitioning problem: given $n$
uniformly random $b$-bit integers $a_1, \ldots, a_n$, certify the non-existence
of a perfect partition, i.e. certify that $\mathsf{disc} (A) \geq 1$ for $A =
(a_1, \ldots, a_n)$. Under the scaling $b = \alpha n$, it is known that the
probability of the existence of a perfect partition undergoes a phase
transition from 1 to 0 at $\alpha = 1$; our algorithm certifies the
non-existence of perfect partitions for some $\alpha = O(n)$. We also give
efficient non-deterministic algorithms with significantly improved guarantees.
Our algorithms involve a reduction to the Shortest Vector Problem.
