A Hadamard matrix of order n is an n\times n, \pm 1 matrix for which every two rows are orthogonal. It is not hard to check that if n is not divisible by 4, then a Hadamard matrix of order n does not exists. On the other hand, it is widely open to prove the existence of Hadamard matrices of order 4n for all n. 

Years of investigation show that Hadamard matrices are very hard to find. In particular, as an easy exercise, one can show that the probability for a random matrix to be Hadamard is at most 2^{-n^2/2+o(n^2)}. 

In this talk I'll convince ourselves that Hadamard matrices are even harder to find! that is, the probability for a random matrix to be Hadamard is at most 2^{(1+\varepsilon)n^2/} for some small (but fixed) epsilon>0. Note that the gain is of the form 2^{-\theta(n^2)}, which, at least according to my knowledge, does not follow from any standard large deviation inequality. 

I'll give a purely combinatorial proof that does not appear on the paper (or elsewhere..) I have with Jain and Zhao on this topic.  This proof was basically our key for giving improved anticoncentration inequalities for classical results by Halasz regarding random sums of vectors (I won't discuss the anticoncentration bounds though...).