  For a binary integer program (IP) $\max c^{\mathsf T} x, Ax \leq b, x \in
\{0,1\}^n$, where $A \in \mathbb{R}^{m \times n}$ and $c \in \mathbb{R}^n$ have
independent Gaussian entries and the right-hand side $b \in \mathbb{R}^m$
satisfies that its negative coordinates have $\ell_2$ norm at most $n/10$, we
prove that the gap between the value of the linear programming relaxation and
the IP is upper bounded by $\operatorname{poly}(m)(\log n)^2 / n$ with
probability at least $1-1/n^7-1/2^{\Omega(m)}$. Our results give a Gaussian
analogue of the classical integrality gap result of Dyer and Frieze (Math. of
O.R., 1989) in the case of random packing IPs. In constrast to the packing
case, our integrality gap depends only polynomially on $m$ instead of
exponentially. By recent breakthrough work of Dey, Dubey and Molinaro (SODA,
2021), the bound on the integrality gap immediately implies that branch and
bound requires $n^{\operatorname{poly}(m)}$ time on random Gaussian IPs with
good probability, which is polynomial when the number of constraints $m$ is
fixed.
