Before revision: For a binary integer program (IP) \max c^{\mathsf T {\rm   x, Ax \leq b, x \in \{0,1\}^n, where A \in R^{m \times n} and c \in R^n have independent Gaussian entries and the right-hand side b \in 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 poly(m)(\log n)^2 / n with probability at least 1-1 /n^7 -1/2 ^{ \Omega (m)}.
After revision: For a binary integer program (IP) \max c^{\mathsf T {\rm x, Ax \leq b, x \in \{0,1\}^n, where A \in R^{m \times n} and c \in R^n have independent Gaussian entries and the right-hand side b \in 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 poly(m)(\log n)^2 / n with probability at least 1-1 /n^7 -1/2 ^{ - (m)}.